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$.