Average-case lower bounds for formula size

Ilan Komargodski, Ran Raz

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

31 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 - 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
Country/TerritoryUnited States
CityPalo Alto, CA
Period6/1/136/4/13

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Average-case hardness
  • Boolean formulas
  • Correlation bounds
  • Demorgan formulas
  • Lower bounds

Fingerprint

Dive into the research topics of 'Average-case lower bounds for formula size'. Together they form a unique fingerprint.

Cite this