# 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: https://video.ias.edu/csdm/2017/1107-EshanChattopadhyay

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