__
TR17-166 | 3rd November 2017 22:51
__

#### A sampling lower bound for permutations

**Abstract:**
A map $f:[n]^{\ell}\to[n]^{n}$ has locality $d$ if each output symbol

in $[n]=\{1,2,\ldots,n\}$ depends only on $d$ of the $\ell$ input

symbols in $[n]$. We show that the output distribution of a $d$-local

map has statistical distance at least $1-2\cdot\exp(-n/\log^{c^{d}}n)$

from a uniform permutation of $[n]$. This seems to be the first lower

bound for the well-studied problem of generating permutations. Because

$\poly(n)$-size AC$^{0}$ circuits can sample almost uniform permutations,

the result also separates AC$^{0}$ sampling from local.

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^{c^{d}}n$

. This is arguably the first lower bound for a natural data structure

problem that is obtained from a sampling lower bound.