Pseudorandomness for Width-2 Branching Programs

Abstract

We show that pseudorandom generators that fool degree-k polynomials over 𝔽2 also fool branching programs of width-2 and polynomial length that read k bits of input at a time. This model generalizes polynomials of degree k over 𝔽2 and includes some other interesting classes of functions, for instance, k-DNFs.

The proof essentially follows by a new decomposition theorem for width-2 branching programs. The theorem states that if f can be computed by a width-2 branching program that reads k bits of input at a time, then f can be (roughly) written as a sum f=∑iαifi where each fi is a degree-k polynomial and ∑i|αi| is small.

Bogdanov and Viola (FOCS 2007) constructed a pseudorandom generator that fools degree-k polynomials over 𝔽2 for arbitrary k. Their construction consists of summing k independent copies of a generator that ϵ-fools linear functions. Our second result investigates the limits of such constructions: We show that, in general, such a construction is not pseudorandom against bounded fan-in circuits of depth O((log(klog1/ϵ))2).