Volume 15 (2019) Article 10 pp. 1-26
CCC 2018 Special Issue

Pseudorandom Generators from Polarizing Random Walks

by Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett

Received: July 2, 2018
Revised: May 21, 2019
Published: October 21, 2019

We propose a new framework for constructing pseudorandom generators for $n$-variate Boolean functions. It is based on two new notions. First, we introduce fractional pseudorandom generators, which are pseudorandom distributions taking values in $[-1,1]^n$. Next, we use a fractional pseudorandom generator as steps of a random walk in $[-1,1]^n$ that converges to $\{-1,1\}^n$. We prove that this random walk converges fast (in time logarithmic in $n$) due to polarization. As an application, we construct pseudorandom generators for Boolean functions with bounded Fourier tails. We use this to obtain a pseudorandom generator for functions with sensitivity $s$, whose seed length is polynomial in $s$. Other examples include functions computed by branching programs of various sorts or by bounded-depth circuits.

------------

A conference version of this paper appeared in the Proceedings of the 33rd Computational Complexity Conference (CCC 2018).

DOI: 10.4086/toc.2019.v015a010

© 2019 Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett
Licensed under a Creative Commons Attribution License (CC-BY)