Avishay Tal: Improved pseudorandomness for unordered branching programs through local monotonicity

PRACTICALITIES

Lunch is served at 12:00 noon (register at tinyurl.com/TCS180409  at the latest the Saturday before, but preferably earlier). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for 1½-2 hours of more technical discussions.

ABSTRACT

We present an explicit pseudorandom generator with polylog(n) seed length for read-once constant-width branching programs that can read their n input bits in any order. This improves upon the work of Impagliazzo, Meka, and Zuckerman (FOCS, 2012), which required seed length \(n^{1/2+o(1)}\).

A central ingredient in our work is a bound on the Fourier spectrum of constant-width branching programs, settling a conjecture posed by Reingold, Steinke, and Vadhan (RANDOM, 2013).