Average-case lower bounds for formula size

Ilan Komargodski, Ran Raz

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

25 Scopus citations

Abstract

We give an explicit function h : {0; 1}n → {0; 1} such that any deMorgan formula of size O(n2.499) agrees with h on at most 1 2 + ε fraction of the inputs, where ε is exponentially small (i.e. ε = 2-nΩ(1) ). We also show, using the same technique, that any boolean formula of size O(n1.999) over the complete basis, agrees with h on at most 1 2 +ε fraction of the inputs, where ε is exponentially small (i.e. ε = 2-nΩ(1) ). Our construction is based on Andreev's (n2.5-o(1)) formula size lower bound that was proved for the case of exact computation [2].

Original languageEnglish (US)
Title of host publicationSTOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing
Pages171-180
Number of pages10
DOIs
StatePublished - Jul 11 2013
Externally publishedYes
Event45th Annual ACM Symposium on Theory of Computing, STOC 2013 - Palo Alto, CA, United States
Duration: Jun 1 2013Jun 4 2013

Publication series

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

Other

Other45th Annual ACM Symposium on Theory of Computing, STOC 2013
CountryUnited States
CityPalo Alto, CA
Period6/1/136/4/13

All Science Journal Classification (ASJC) codes

  • Software

Cite this

Komargodski, I., & Raz, R. (2013). Average-case lower bounds for formula size. In STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing (pp. 171-180). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2488608.2488630