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 language | English (US) |
|---|---|
| Title of host publication | STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing |
| Pages | 171-180 |
| Number of pages | 10 |
| DOIs | |
| State | Published - Jul 11 2013 |
| Externally published | Yes |
| Event | 45th Annual ACM Symposium on Theory of Computing, STOC 2013 - Palo Alto, CA, United States Duration: Jun 1 2013 → Jun 4 2013 |
Publication series
| Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
|---|---|
| ISSN (Print) | 0737-8017 |
Other
| Other | 45th Annual ACM Symposium on Theory of Computing, STOC 2013 |
|---|---|
| Country | United States |
| City | Palo Alto, CA |
| Period | 6/1/13 → 6/4/13 |
All Science Journal Classification (ASJC) codes
- Software
Cite this
Komargodski, I., & Raz, R. (2013). Average-case lower bounds for formula size. In STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing (pp. 171-180). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2488608.2488630