__
TR18-060 | 6th April 2018 16:47
__

#### Sampling lower bounds: boolean average-case and permutations

**Abstract:**
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$.