Randomness-efficient sampling within NC1

We construct a randomness-efficient averaging sampler that is computable by uniform constant-depth circuits with parity gates (i.e., in uniform AC(0)[circle plus]). Our sampler matches the parameters achieved by random walks on constant-degree expander graphs, allowing us to apply a variety expander-based techniques within NC1. For example, we obtain the following results: Randomness-efficient error-reduction for uniform probabilistic NC1, TC0, AC(0) [circle plus] 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 6 using r + O(log(1/delta)) random bits. An optimal bitwise E-biased generator in AC(0)[G)]: There exists a 1/2(Omega(n))-biased generator G : {0, 1}(O(n)) -> {0, 1}(2n) for which poly(n)-size uniform AC(0)[circle plus] circuits can compute G(s)(i) given (s, i) is an element of { 0, 1}(O(n)) X {0, 1}(n). This resolves a question raised by Gutfreund and Viola (Random 2004). uniform BP center dot AC(0) subset of 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 give an elementary proof of a generalization of Gillman's Chernoff Bound for Expander Walks (SIAM Journal on Computing 1998).