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