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