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