Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-060 | 6th April 2018 16:47

Sampling lower bounds: boolean average-case and permutations


Authors: Emanuele Viola
Publication: 6th April 2018 16:47
Downloads: 103


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

ISSN 1433-8092 | Imprint