ECCC-Report TR18-209https://eccc.weizmann.ac.il/report/2018/209Comments and Revisions published for TR18-209en-usSat, 08 Dec 2018 02:28:19 +0200
Paper TR18-209
| AC0 unpredictability |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2018/209We prove that for every distribution $D$ on $n$ bits with Shannon
entropy $\ge n-a$ at most $O(2^{d}a\log^{d+1}g)/\gamma{}^{5}$ of
the bits $D_{i}$ can be predicted with advantage $\gamma$ by an
AC$^{0}$ circuit of size $g$ and depth $d$ that is a function of
all the bits of $D$ except $D_{i}$. This answers a question by Meir
and Wigderson (2017) who proved a corresponding result for decision
trees.
We also show that there are distributions $D$ with entropy $\ge n-O(1)$
such that any subset of $O(n/\log n)$ bits of $D$ on can be distinguished
from uniform by a circuit of depth $2$ and size $\poly(n)$. This
separates the notions of predictability and distinguishability in
this context.
Sat, 08 Dec 2018 02:28:19 +0200https://eccc.weizmann.ac.il/report/2018/209