TY - GEN
T1 - Average-case lower bounds for formula size
AU - Komargodski, Ilan
AU - Raz, Ran
PY - 2013/7/11
Y1 - 2013/7/11
N2 - 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].
AB - 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].
UR - http://www.scopus.com/inward/record.url?scp=84879824838&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84879824838&partnerID=8YFLogxK
U2 - 10.1145/2488608.2488630
DO - 10.1145/2488608.2488630
M3 - Conference contribution
AN - SCOPUS:84879824838
SN - 9781450320290
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 171
EP - 180
BT - STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing
T2 - 45th Annual ACM Symposium on Theory of Computing, STOC 2013
Y2 - 1 June 2013 through 4 June 2013
ER -