ECCC-Report TR15-065https://eccc.weizmann.ac.il/report/2015/065Comments and Revisions published for TR15-065en-usSun, 19 Apr 2015 17:09:33 +0300
Paper TR15-065
| An average-case depth hierarchy theorem for Boolean circuits |
Benjamin Rossman,
Rocco Servedio,
Li-Yang Tan
https://eccc.weizmann.ac.il/report/2015/065We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every $d \geq 2$, there is an explicit $n$-variable Boolean function $f$, computed by a linear-size depth-$d$ formula, which is such that any depth-$(d-1)$ circuit that agrees with $f$ on $(1/2 + o_n(1))$ fraction of all inputs must have size $\exp({n^{\Omega(1/d)}}).$ This answers an open question posed by H{\aa}stad in his Ph.D. thesis.
Our average-case depth hierarchy theorem implies that the polynomial hierarchy is infinite relative to a random oracle with probability 1, confirming a conjecture of H{\aa}stad, Cai, and Babai. We also use our result to show that there is no "approximate converse" to the results of Linial, Mansour, Nisan and Boppana on the total influence of small-depth circuits, thus answering a question posed by O'Donnell, Kalai, and Hatami.
A key ingredient in our proof is a notion of \emph{random projections} which generalize random restrictions.Sun, 19 Apr 2015 17:09:33 +0300https://eccc.weizmann.ac.il/report/2015/065