Summary: We show that pseudorandom generators that fool degree-\(k\) polynomials over \(\mathbb{F}_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 \(\mathbb{F}_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=\sum_i \alpha_i f_i\), where each \(f\) is a degree-\(k\) polynomial and \(\sum_i|\alpha_i|\) is small.
A. Bogdanov and B. Viola [SIAM J. Comput. 39, No. 6, 2464–2486 (2010; Zbl 1211.68215)] constructed a pseudorandom generator that fools degree-\(k\) polynomials over \(\mathbb{F}_2\) for arbitrary \(k\). Their construction consists of summing \(k\) independent copies of a generator that \(\varepsilon\)-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(k\log 1/\varepsilon))^2)\).