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 \emph{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$ non-adaptive probes must use
space $\ge\log_{2}n!+n/\log^{\exp(O(d))}n$.

Improved statistical distance from quasipolynomially close to 1/2 to exponentially close to 1/2. Many other minor changes.

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 \emph{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 $\ge1/2-1/n^{\Omega(\log n)}$ 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$ non-adaptive probes must use
space $\ge\log_{2}n!+n/\log^{\exp(d)}n$.