Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Average-case lower bounds for De Morgan Formula Size
event speaker icon
Ilan Komargodski (Weizmann Institute of Science)
event date icon
Wednesday, 20.11.2013, 12:30
event location icon
Taub 201
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)