Revised: December 26, 2019
Published: October 9, 2020
Abstract: [Plain Text Version]
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 $\eps$ we obtain seed length $\tilde O(\log(m/\eps)\log(1/\eps))$. This is optimal up to a factor of $\log(1/\eps)\cdot \poly\log\log(m/\eps)$. The previous best seed length was polylogarithmic in $m$ and $1/\eps$.
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^\ell\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 $\ell \cdot \polylog (m/\eps)$. This implies better generators for other classes of tests. If moreover the $f_i$ have output range $\{-1, 0, 1\}$ then we obtain seed length $\tilde O((\log(k/\eps) + \ell) (\log(1/\eps) + \log\log m))$. This is again optimal up to a factor of $\log(1/\eps) \cdot \polylog(\ell, \log k, \log m, \log(1/\eps))$, 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.
Licensed under a Creative Commons Attribution License (CC-BY)