Revised: May 21, 2019
Published: October 21, 2019
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).
Licensed under a Creative Commons Attribution License (CC-BY)