Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR16-041 | 17th March 2016 14:49

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

TR16-041
Publication: 17th March 2016 14:49
Keywords:

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.

ISSN 1433-8092 | Imprint