TY - GEN
T1 - Improved average-case lower bounds for demorgan formula size
AU - Komargodski, Ilan
AU - Raz, Ran
AU - Tal, Avishay
PY - 2013
Y1 - 2013
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
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
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 -