Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR06-058 | 24th August 2006 00:00

Randomness-Efficient Sampling within NC^1 Revision of: TR06-058

RSS-Feed




Revision #1
Authors: Alexander D. Healy
Accepted on: 24th August 2006 00:00
Downloads: 3474
Keywords: 


Abstract:

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


Paper:

TR06-058 | 25th April 2006 00:00

Randomness-Efficient Sampling within NC^1





TR06-058
Authors: Alexander Healy
Publication: 29th April 2006 03:45
Downloads: 3427
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint