ECCC-Report TR18-015https://eccc.weizmann.ac.il/report/2018/015Comments and Revisions published for TR18-015en-usMon, 30 Apr 2018 16:29:08 +0300
Revision 1
| Pseudorandom Generators from Polarizing Random Walks |
Eshan Chattopadhyay,
Pooya Hatami,
Kaave Hosseini,
Shachar Lovett
https://eccc.weizmann.ac.il/report/2018/015#revision1We 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. Mon, 30 Apr 2018 16:29:08 +0300https://eccc.weizmann.ac.il/report/2018/015#revision1
Comment 1
| Open problem 1.8 |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2018/015#comment1The answer to Open problem 1.8 is no. See https://eccc.weizmann.ac.il/report/2015/182/Mon, 29 Jan 2018 11:20:50 +0200https://eccc.weizmann.ac.il/report/2018/015#comment1
Paper TR18-015
| Pseudorandom Generators from Polarizing Random Walks |
Eshan Chattopadhyay,
Pooya Hatami,
Kaave Hosseini,
Shachar Lovett
https://eccc.weizmann.ac.il/report/2018/015We 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. Thu, 25 Jan 2018 22:18:51 +0200https://eccc.weizmann.ac.il/report/2018/015