### Abstract

We give an explicit function h : {0; 1}^{n} → {0; 1} such that any deMorgan formula of size O(n^{2.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(n^{1.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 (n^{2.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