The Taub Faculty of Computer Science Events and Talks

Average-case lower bounds for De Morgan Formula Size.

We give a function $h:{0,1}^n \to {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^{-\Omega(r)}$ of the inputs.

Our technical contributions include a theorem that shows that the ``expected shrinkage'' result of H{\aa}stad actually holds with very high probability, where the restrictions are chosen from a certain distribution that takes into account the structure of the formula.

The talk is based on two papers:

- Improved average-case lower bounds for DeMorgan formula size (with Ran Raz and Avishay Tal)
- Average-case lower bounds for formula size - (with Ran Raz)