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 uniform probabilistic circuits with error

δ

using

r

+

O

(log(1/

δ

)) random bits.

Optimal explicit

ε

-biased generator in

AC

0

[⊕]: There is a 1/2

Ω(

n

)

-biased generator

$G:{0, 1}^{O(n)} \to {0, 1}^{2^n}$

for which poly(

n

)-size uniform

AC

0

[⊕] circuits can compute

G

(

s

)

i

given (

s

,

i

) ∈0, 1

O

(

n

)

×0, 1

n

. This resolves a question raised by Gutfreund & 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 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

).