Advances in Boolean Function Analysis — Pseudorandom Generators from Polarizing Random Walks

This talk is part of the Advances in Boolean Function Analysis Lecture Series. The series will feature weekly two-hour lectures that aim to address both the broad context of the result and the technical details. Though closely related in theme, each lecture will be self-contained. Join us weekly at 10:00 a.m. PDT, from July 15, 2020 to August 18, 2020. There is a five minute break at the end of the first hour. 

Abstract:

This talk is concerned with a new framework for constructing pseudorandom generators (PRGs) for n-variate Boolean functions. The framework relies on two notions. First is a generalization of PRGs

called a fractional PRG, which is a pseudorandom distribution taking values in [-1,1]^n. Next, we show that a fractional PRG that satisfies certain nontriviality conditions can be used as steps to a polarizing random walk that converges to {-1,1}^n quickly. This allows us to reduce the task of constructing PRGs to constructing fractional PRGs.



We will demonstrate the power of this framework by constructing fractional PRGs from various bounds on the Fourier coefficients of a family of Boolean functions.



This talk is based on joint work with Eshan Chattopadhyay, Kaave Hosseini, and Shachar Lovett.