Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-015 | 30th April 2018 16:29

Pseudorandom Generators from Polarizing Random Walks

RSS-Feed




Revision #1
Authors: Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett
Accepted on: 30th April 2018 16:29
Downloads: 2502
Keywords: 


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.


Paper:

TR18-015 | 25th January 2018 21:44

Pseudorandom Generators from Polarizing Random Walks


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.


Comment(s):

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

Open problem 1.8

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


Comment:

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




ISSN 1433-8092 | Imprint