Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR17-167 | 3rd November 2017 22:57

More on bounded independence plus noise: Pseudorandom generators for read-once polynomials


Authors: Chin Ho Lee, Emanuele Viola
Publication: 3rd November 2017 22:57
Downloads: 142


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

ISSN 1433-8092 | Imprint