pdf icon
Volume 16 (2020) Article 7 pp. 1-50
More on Bounded Independence Plus Noise: Pseudorandom Generators for Read-Once Polynomials
Received: March 30, 2019
Revised: December 26, 2019
Published: October 9, 2020
Download article from ToC site:
[PDF (427K)] [PS (2889K)] [Source ZIP]
Keywords: pseudorandom generators, bounded independence plus noise, branching programs, read-once polynomials
ACM Classification: G.3
AMS Classification: 68Q87, 68W20

Abstract: [Plain Text Version]

$ \newcommand{\C}{{\mathbb C}} \newcommand{\zo}{\{0,1\}} \def\eps{\varepsilon} \def\poly{\mathrm{poly}} \def\polylog{\mathrm{polylog}} $

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.