Randomness-Efficient Sampling Within NC~1

摘要

We construct a randomness-efficient averaging sampler that is computable by uniform constant-depth circuits with parity gates (i.e., in uniform AC~0[⊕]). Our sampler matches the parameters achieved by random walks on constant-degree expander graphs, allowing us to apply a variety expander-based techniques within NC~1. For example, we obtain the following results: 1. Randomness-efficient error-reduction for uniform probabilistic NC~1, TC~0, AC~0[⊕] and AC~0: Any function computable by uniform probabilistic circuits with error 1/3 using r random bits is computable by uniform probabilistic circuits with error δ using r + O(log(1/δ)) random bits. 2. Optimal explicit ε-biased generator in AC~0[⊕]: There is a 1/2~(Ω(n))-biased generator G : {0, 1}~(O(n)) → {0,1}~(2~n) for which poly(n)-size uniform AC~0[⊕] circuits can compute G(s)_i given (s, i) ∈ {0,1}~(O(n)) x {0, 1}~n. This resolves a question raised by Gutfreund & Viola (Random 2004). 3. uniform BP · AC~0 is contained in uniform AC~0/O(n). Our sampler is based on the zig-zag graph product of Reingold, Vadhan and Wigderson (Annals of Math 2002) and as part of our analysis we give an elementary proof of a generalization of Gillman's Chernoff Bound for Expander Walks (FOCS 1994).