We construct a randomness-efficient averaging sampler that
is computable by uniform constant-depth circuits with parity gates
(i.e., in AC^0[mod 2]). 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[mod 2] 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 delta using r
+ O(log(1/delta)) random bits.
- An optimal explicit epsilon-biased generator in AC^0[mod 2]: There
exists a 1/2^{Omega(n)}-biased generator G:{0,1}^{O(n)} to {0,1}^{2^n}
for which poly(n)-size AC^0[mod 2] circuits can compute G(s)_i given
(s, i) in {0,1}^{O(n)} times {0,1}^n. This resolves a question raised
by Gutfreund and Viola (Random 2004).
- uniform BPAC^0 subseteq 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).
We construct a randomness-efficient averaging sampler that is computable by uniform constant-depth circuits with parity gates (i.e., in AC^0[mod 2]). 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[mod 2] 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 \delta using O(r + log(1/\delta)) random bits.
- An optimal explicit \epsilon-biased generator in AC^0[mod 2]: There exists a 1/2^{\Omega(n)}-biased generator G:{0,1}^{O(n)} \to {0,1}^{2^n} for which poly(n)-size AC^0[mod 2] circuits can compute G(s)_i given (s,
i) \in {0,1}^{O(n)} \times {0,1}^n. This resolves a question raised by Gutfreund and Viola (Random 2004).
- uniform BPAC^0 \subseteq 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 1998).
