Revision #1 Authors: Alexander D. Healy

Accepted on: 24th August 2006 00:00

Downloads: 1535

Keywords:

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).