Pseudorandom generators for unordered branching programs

We present an explicit pseudorandom generator with seed length $\tilde{O}((\log n)^{w+1})$ for read-once, oblivious, width $w$ branching programs that can read their input bits in any order. This improves upon the work of Impaggliazzo, Meka and Zuckerman where they required seed length $n^{1/2+o(1)}$.

A central ingredient in our work is the following bound that we prove on the Fourier spectrum of branching programs. For any width $w$ (read-once, oblivious) branching program $B:\{0,1\}^n\rightarrow \{0,1\}$, any $k \in \{1,\ldots,n\}$, \[\sum_{S: |S|=k}|\widehat{B}(S)| \le O((\log n)^{wk}).\] This settles a conjecture posed by Reingold, Steinke, and Vadhan.

(Based on joint work with Pooya Hatami, Omer Reingold, and Avishay Tal.)