pdf icon
Volume 15 (2019) Article 10 pp. 1-26
CCC 2018 Special Issue
Pseudorandom Generators from Polarizing Random Walks
Received: July 2, 2018
Revised: May 21, 2019
Published: October 21, 2019
Download article from ToC site:
[PDF (296K)] [PS (1665K)] [Source ZIP]
Keywords: pseudorandom generator, random walk
ACM Classification: F.1.3
AMS Classification: 68Q17

Abstract: [Plain Text Version]

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