### Abstract

We give an explicit function h : {0, 1}^{n} → {0, 1} such that every deMorgan formula of size n^{3-o(1)}/r^{2} 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 | |

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 | United States |

City | Berkeley, CA |

Period | 10/27/13 → 10/29/13 |

### All Science Journal Classification (ASJC) codes

- Computer Science(all)

## Cite this

*Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013*(pp. 588-597). [6686195] https://doi.org/10.1109/FOCS.2013.69