Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-015 | 25th January 2018 21:44

Pseudorandom Generators from Polarizing Random Walks



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.


Comment #1 to TR18-015 | 29th January 2018 11:20

Open problem 1.8

Authors: Emanuele Viola
Accepted on: 29th January 2018 11:20


The answer to Open problem 1.8 is no. See https://eccc.weizmann.ac.il/report/2015/182/

ISSN 1433-8092 | Imprint