Theory of Computing
-------------------
Title : Pseudorandom Generators from Polarizing Random Walks
Authors : Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett
Volume : 15
Number : 10
Pages : 1-26
URL : https://theoryofcomputing.org/articles/v015a010
Abstract
--------
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).