Sampling Lower Bounds: Boolean Average-Case and Permutations
Emanuele Viola · SIAM Journal on Computing · 2020
We show that for every small AC$^{0}$ circuit $C:\{0,1\}^{\ell}\to\{0,1\}^{m}$ there exists a multiset $S$ of $2^{m-m^{\Omega(1)}}$ restrictions that preserve the output distribution of $C$ and, moreover, polarize min-entropy: the restriction of $C$ to any $r\in S$ either is constant or has polynomial min-entropy. This structural result is then applied to exhibit an explicit boolean function $h:\{0,1\}^{n}\to\{0,1\}$ such that for every small AC$^{0}$ circuit $C:\{0,1\}^{\ell}\to\{0,1\}^{n+1}$ the output distribution of $C$ for a uniform input has statistical distance exponentially close to $1/2$ from the distribution $(U,h(U))$ for $U$ uniform in $\{0,1\}^{n}$. Previous such “sampling lower bounds” either gave exponentially small statistical distance or applied to functions $h$ with large output length. We also show that the output distribution of a $d$-local map $f:[n]^{\ell}\to[n]^{n}$ for a uniform input has statistical distance at least $1-2\cdot\exp(-n/\log^{\exp(O(d))}n)$ from a uniform permutation of $[n]$. Here $d$-local means that each output symbol in $[n]=\{1,2,\ldots,n\}$ depends only on $d$ of the $\ell$ input symbols in $[n]$. This separates AC$^{0}$ sampling from local, because small AC$^{0}$ circuits can sample almost uniform permutations. As an application, we prove that any cell-probe data structure for storing permutations $\pi$ of $n$ elements such that $\pi(i)$ can be retrieved with $d$ nonadaptive probes must use space $\ge\log_{2}n!+n/\log^{\exp(O(d))}n$.