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: 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 circuits of the same type with error δ using r + O(log(1/δ)) random bits. An optimal bitwise biased generator in AC 0[]: There exists a 1/2Ω(n)-biased generator G : {0, 1} O(n) - {0, 1}2n 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 question raised by Gutfreund and Viola (Random 2004). uniform BP . AC 0 uniform AC 0/O(n). Our sampler is based on the zig-zag graph product of Reingold, Vadhan & Wigderson (Annals of Math 2002) and as part of our analysis we givean elementary proof of a generalization of Gillman's Chernoff Bound for Expander Walks (SIAM Journal on Computing 1998).