Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-041 | 17th March 2016 14:49

An average-case depth hierarchy theorem for higher depth

RSS-Feed




TR16-041
Authors: Johan Håstad
Publication: 17th March 2016 14:49
Downloads: 1859
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