Higher lower bounds on monotone size

Danny Harnik, Ran Raz

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

19 Scopus citations

Abstract

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
Pages378-387
Number of pages10
DOIs
StatePublished - Dec 1 2000
Externally publishedYes
Event32nd Annual ACM Symposium on Theory of Computing, STOC 2000 - Portland, OR, United States
Duration: May 21 2000May 23 2000

Other

Other32nd Annual ACM Symposium on Theory of Computing, STOC 2000
CountryUnited States
CityPortland, OR
Period5/21/005/23/00

All Science Journal Classification (ASJC) codes

  • Software

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

Cite this