An Average-Case Depth Hierarchy Theorem for Boolean Circuits.
B. Rossman and R. Servedio and L.-Y. Tan.
In 56th Annual Symposium on Foundations of Computer Science (FOCS), 2015, pp. 1030--1048.
Best Paper Award, FOCS 2015.


We 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åstad in his Ph.D. thesis (1986).

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åstad (1986), Cai (1986) and Babai (1987). We also use our result to show that there is no ``approximate converse'' to the results of Linial, Mansour, Nisan (1993) and Boppana (1997) on the total influence of small-depth circuits, thus answering a question posed by O'Donnell (2007), Kalai (2012), and Hatami (2014).

A key ingredient in our proof is a notion of random projections which generalize random restrictions.

Link to conference version

Link to ArXiV version

Back to main papers page