Talks
Spring 2017

# Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity

Thursday, June 21st, 2018 9:30 am10:15 am

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 Impagliazzo, 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\subseteq[n]: |S|=k}|\widehat{B}(S)| \le O(\log n)^{wk}.$$ This settles a conjecture posed by Reingold, Steinke, and Vadhan.