Revision #1 Authors: Chin Ho Lee, Emanuele Viola

Accepted on: 6th April 2018 16:41

Downloads: 724

Keywords:

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.

Improved bounds for bounded independence plus noise, and changes to exposition

TR17-167 Authors: Chin Ho Lee, Emanuele Viola

Publication: 3rd November 2017 22:57

Downloads: 818

Keywords:

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.