On the size complexity of monotone formulas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

"Monotone" formulas, i.e. formulas using positive constants, additions and multiplications are investigated. Lower bounds on the size of monotone formulas representing specific polynomials (permanent, matrix multiplication, symmetric functions) are achieved, using a general, dynamic programming approach. These bounds are tight for the cases investigated. Some generalizations are suggested.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 7th Colloquium
EditorsJaco de Bakker, Jan van Leeuwen
PublisherSpringer-Verlag
Pages621-631
Number of pages11
ISBN (Print)9783540100034
DOIs
StatePublished - Jan 1 1980
Externally publishedYes
Event7th International Colloquium on Automata, Languages and Programming, ICALP 1980 - Noordwijkerhout, Netherlands
Duration: Jul 14 1980Jul 18 1980

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume85 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other7th International Colloquium on Automata, Languages and Programming, ICALP 1980
CountryNetherlands
CityNoordwijkerhout
Period7/14/807/18/80

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On the size complexity of monotone formulas'. Together they form a unique fingerprint.

Cite this