Improved average-case lower bounds for demorgan formula size

Ilan Komargodski; Ran Raz; Avishay Tal

doi:10.1109/FOCS.2013.69

Improved average-case lower bounds for demorgan formula size

Ilan Komargodski, Ran Raz, Avishay Tal

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

33 Scopus citations

Abstract

We give an explicit function h : {0, 1}ⁿ → {0, 1} such that every deMorgan formula of size n^3-o(1)/r² 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 language	English (US)
Title of host publication	Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
Pages	588-597
Number of pages	10
DOIs	https://doi.org/10.1109/FOCS.2013.69
State	Published - Dec 1 2013
Externally published	Yes
Event	2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 - Berkeley, CA, United States Duration: Oct 27 2013 → Oct 29 2013

Other

Other	2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
Country/Territory	United States
City	Berkeley, CA
Period	10/27/13 → 10/29/13

All Science Journal Classification (ASJC) codes

Computer Science(all)

Access to Document

10.1109/FOCS.2013.69

Cite this

@inproceedings{5d6dc72e352b413b999eab28d7d2892b,

title = "Improved average-case lower bounds for demorgan formula size",

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.",

author = "Ilan Komargodski and Ran Raz and Avishay Tal",

year = "2013",

month = dec,

day = "1",

doi = "10.1109/FOCS.2013.69",

language = "English (US)",

isbn = "9780769551357",

pages = "588--597",

booktitle = "Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013",

note = "2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 ; Conference date: 27-10-2013 Through 29-10-2013",

}

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., 6686195, pp. 588-597, 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013, Berkeley, CA, United States, 10/27/13. https://doi.org/10.1109/FOCS.2013.69

TY - GEN

T1 - Improved average-case lower bounds for demorgan formula size

AU - Komargodski, Ilan

AU - Raz, Ran

AU - Tal, Avishay

PY - 2013/12/1

Y1 - 2013/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84893443727&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893443727&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2013.69

DO - 10.1109/FOCS.2013.69

M3 - Conference contribution

AN - SCOPUS:84893443727

SN - 9780769551357

SP - 588

EP - 597

BT - Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013

T2 - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013

Y2 - 27 October 2013 through 29 October 2013

ER -

Improved average-case lower bounds for demorgan formula size

Abstract

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Cite this