ECCC-Report TR17-166https://eccc.weizmann.ac.il/report/2017/166Comments and Revisions published for TR17-166en-usFri, 03 Nov 2017 22:52:07 +0200
Paper TR17-166
| A sampling lower bound for permutations |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2017/166A 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.
Fri, 03 Nov 2017 22:52:07 +0200https://eccc.weizmann.ac.il/report/2017/166