Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR17-166 | 3rd November 2017 22:51

A sampling lower bound for permutations

RSS-Feed




TR17-166
Authors: Emanuele Viola
Publication: 3rd November 2017 22:52
Downloads: 1288
Keywords: 


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.



ISSN 1433-8092 | Imprint