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.

Abstract:

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.