__
TR16-041 | 17th March 2016 14:49
__

#### An average-case depth hierarchy theorem for higher depth

**Abstract:**
We extend the recent hierarchy results of Rossman, Servedio and

Tan \cite{rst15} to any $d \leq \frac {c \log n}{\log {\log n}}$

for an explicit constant $c$.

To be more precise, we prove that for any such $d$ there is a function

$F_d$ that is computable by a read-once formula of depth $d$ but

such that any circuit of depth $d-1$ and size at most $2^{O(n^{1/5d})}$

agrees with $F_d$ on a fraction at most $\frac 12 + O(n^{-1/8d})$ of

inputs.