The monotone circuit complexity of boolean functions

Noga Alon, Ravi B. Boppana

Research output: Contribution to journalArticlepeer-review

233 Scopus citations

Abstract

Recently, Razborov obtained superpolynomial lower bounds for monotone circuits that cliques in graphs. In particular, Razborov showed that detecting cliques of size s in a graph m vertices requires monotone circuits of size Ω(m s /(log m)2 s ) for fixed s, and size m Ω(log m) for m/4]. In this paper we modify the arguments of Razborov to obtain exponential lower bounds for circuits. In particular, detecting cliques of size (1/4) (m/log m)2/3 requires monotone circuits exp (Ω((m/log m)1/3)). For fixed s, any monotone circuit that detects cliques of size s requires m) s ) AND gates. We show that even a very rough approximation of the maximum clique of a graph requires superpolynomial size monotone circuits, and give lower bounds for some Boolean functions. Our best lower bound for an NP function of n variables is exp (Ω(n 1/4 · (log n)1/2)), improving a recent result of exp (Ω(n 1/8-ε)) due to Andreev.

Original languageEnglish (US)
Pages (from-to)1-22
Number of pages22
JournalCombinatorica
Volume7
Issue number1
DOIs
StatePublished - Mar 1987
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Keywords

  • AMS subject classification (1980): 68E10, 68C25

Fingerprint

Dive into the research topics of 'The monotone circuit complexity of boolean functions'. Together they form a unique fingerprint.

Cite this