We show that for every small AC 0 circuit C : 0 1 0 1 m there exists a multiset S of 2 m ? m (1) restrictions that preserve the output distribution of C and moreover emph{polarize min-entropy: }the restriction of C to any r 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 0 1 such that for every small AC 0 circuit C : 0 1 0 1 n +1 the output distribution of C for a uniform input has statistical distance 1 2 ? 1 n ( 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 ] [ n ] n for a uniform input has statistical distance at least 1 ? 2 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 n depends only on d of the 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 of n elements such that ( i ) can be retrieved with d non-adaptive probes must use space log 2 n ! + n log exp ( d ) n .
展开▼
