ECCC-Report TR16-041https://eccc.weizmann.ac.il/report/2016/041Comments and Revisions published for TR16-041en-usThu, 17 Mar 2016 14:49:49 +0200
Paper TR16-041
| An average-case depth hierarchy theorem for higher depth |
Johan HÃ¥stad
https://eccc.weizmann.ac.il/report/2016/041We 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.Thu, 17 Mar 2016 14:49:49 +0200https://eccc.weizmann.ac.il/report/2016/041