ECCC-Report TR17-167https://eccc.weizmann.ac.il/report/2017/167Comments and Revisions published for TR17-167en-usFri, 06 Apr 2018 16:41:02 +0300
Revision 1
| More on bounded independence plus noise: Pseudorandom generators for read-once polynomials |
Chin Ho Lee,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2017/167#revision1We construct pseudorandom generators with improved seed length for
several classes of tests. First we consider the class of read-once
polynomials over GF(2) in $m$ variables. For error $\e$ we obtain seed
length $\tilde O (\log(m/\e)) \log(1/\e)$, where $\tilde O$ hides lower-order
terms. This is optimal up to the factor $\tilde O(\log(1/\e))$. The previous
best seed length was polylogarithmic in $m$ and $1/\e$.
Second we consider product tests $f\colon \zo^m \to \C_{\le 1}$. These
tests are the product of $k$ functions $f_i\colon \zo^n \to \C_{\le 1}$,
where the inputs of the $f_i$ are disjoint subsets of the $m$ variables and
$\C_{\le 1}$ is the complex unit disk. Here we obtain seed length $n \cdot
\poly \log (m/\e)$. This implies better generators for other classes of tests.
If moreover the $f_i$ have outputs independent of $n$ and $k$ (e.g.,
$\pmone$) then we obtain seed length $\tilde O(n + \log(k/\e)) \log(1/\e)$.
This is again optimal up to the factor $\tilde O(\log 1/\e)$, while the
previous best seed length was $\ge \sqrt k$.
A main component of our proofs is showing that these classes of tests are
fooled by almost $d$-wise independent distributions perturbed with noise.Fri, 06 Apr 2018 16:41:02 +0300https://eccc.weizmann.ac.il/report/2017/167#revision1
Paper TR17-167
| More on bounded independence plus noise: Pseudorandom generators for read-once polynomials |
Chin Ho Lee,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2017/167We construct pseudorandom generators with improved seed length for
several classes of tests. First we consider the class of read-once
polynomials over GF(2) in $m$ variables. For error $\e$ we obtain seed
length $\tilde O (\log(m/\e)) \log(1/\e)$, where $\tilde O$ hides lower-order
terms. This is optimal up to the factor $\tilde O(\log(1/\e))$. The previous
best seed length was polylogarithmic in $m$ and $1/\e$.
Second we consider product tests $f\colon \zo^m \to \C_{\le 1}$. These
tests are the product of $k$ functions $f_i\colon \zo^n \to \C_{\le 1}$,
where the inputs of the $f_i$ are disjoint subsets of the $m$ variables and
$\C_{\le 1}$ is the complex unit disk. Here we obtain seed length $n \cdot
\poly \log (m/\e)$. This implies better generators for other classes of tests.
If moreover the $f_i$ have outputs independent of $n$ and $k$ (e.g.,
$\pmone$) then we obtain seed length $\tilde O(n + \log(k/\e)) \log(1/\e)$.
This is again optimal up to the factor $\tilde O(\log 1/\e)$, while the
previous best seed length was $\ge \sqrt k$.
A main component of our proofs is showing that these classes of tests are
fooled by almost $d$-wise independent distributions perturbed with noise.Fri, 03 Nov 2017 22:57:40 +0200https://eccc.weizmann.ac.il/report/2017/167