Pseudorandom generators for unordered branching programs

Computer Science/Discrete Mathematics Seminar II
Topic:Pseudorandom generators for unordered branching programs
Speaker:Eshan Chattopadhyay
Affiliation:Member, School of Mathematics
Date:Tuesday, November 7
Time/Room:10:30am - 12:30pm/West Building Lecture Hall
Video Link:

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