Improved average-case lower bounds for demorgan formula size

Ilan Komargodski, Ran Raz, Avishay Tal

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 every deMorgan formula of size n3-o(1)/r2 agrees with h on at most a fraction of 1/2 + 2 -Ω(r)of the inputs. This improves the previous averagecase lower bound of Komargodski and Raz (STOC, 2013). Our technical contributions include a theorem that shows that the "expected shrinkage" result of Hastad (SIAM J. Comput., 1998) actually holds with very high probability (where the restrictions are chosen from a certain distribution that takes into account the structure of the formula), combining ideas of both Impagliazzo, Meka and Zuckerman (FOCS, 2012) and Komargodski and Raz. In addition, using a bit-fixing extractor in the construction of h allows us to simplify a major part of the analysis of Komargodski and Raz.

Original languageEnglish (US)
Title of host publicationProceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
Pages588-597
Number of pages10
DOIs
StatePublished - Dec 1 2013
Externally publishedYes
Event2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 - Berkeley, CA, United States
Duration: Oct 27 2013Oct 29 2013

Other

Other2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
CountryUnited States
CityBerkeley, CA
Period10/27/1310/29/13

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Cite this

Komargodski, I., Raz, R., & Tal, A. (2013). Improved average-case lower bounds for demorgan formula size. In Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 (pp. 588-597). [6686195] https://doi.org/10.1109/FOCS.2013.69