Higher lower bounds on monotone size

Danny Harnik, Ran Raz

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

28 Scopus citations


We prove a lower bound of 2Ω((n/log n)1/3) on the monotone size of an explicit function in monotone-NP (where n is the number of input variables). This is higher than any previous lower bound on the monotone size of a function. The previous best being a lower bound of about 2 Ω(n 1/4) for Andreev's function, proved in [AlBo87]. Our lower bound is proved by the symmetric version of Razborov's method of approximations. However, we present this method in a new and simpler way: Rather than building approximator functions for all the gates in a circuit, we use a gate elimination argument that is based on a Monotone Switching Lemma. The bound applies for a family of functions, each defined by a construction of a small probability space of c-wise independent random variables.

Original languageEnglish (US)
Title of host publicationProceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000
Number of pages10
StatePublished - 2000
Externally publishedYes
Event32nd Annual ACM Symposium on Theory of Computing, STOC 2000 - Portland, OR, United States
Duration: May 21 2000May 23 2000

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


Other32nd Annual ACM Symposium on Theory of Computing, STOC 2000
Country/TerritoryUnited States
CityPortland, OR

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'Higher lower bounds on monotone size'. Together they form a unique fingerprint.

Cite this