Loading jsMath...
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: 2105
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