Theory of Computing
-------------------
Title : Some Limitations of the Sum of Small-Bias Distributions
Authors : Chin Ho Lee and Emanuele Viola
Volume : 13
Number : 16
Pages : 1-23
URL : https://theoryofcomputing.org/articles/v013a016
Abstract
--------
We present two approaches to constructing $\eps$-biased distributions
$D$ on $n$ bits and functions $f : \{0,1\}^n \to \{0,1\}$ such
that the XOR of two independent copies ($D+D$) does not fool $f$.
Using them, we give constructions for any of the following choices:
1. $\eps = 2^{-\Omega(n)}$ and $f$ is in P/poly;
2. $\eps = 2^{-\Omega(n/\log n)}$ and $f$ is in NC^2;
3. $\eps = n^{-c}$ and $f$ is a one-way space $O(c \log n)$ algorithm, for any $c$;
4. $\eps = n^{-\Omega(1)}$ and $f$ is a $\Mod 3$ linear function. All the results give one-sided distinguishers, and extend to the XOR of more copies for suitable $\eps$. We also give conditional results for AC^0 and DNF formulas.
Meka and Zuckerman (RANDOM 2009) prove 4 with $\eps = O(1)$. Bogdanov,
Dvir, Verbin, and Yehudayoff (Theory of Computing, 2013) prove 2 with
$\eps = 2^{-O(\sqrt{n})}$. Chen and Zuckerman (personal communication)
give an alternative proof of 3.
---
A preliminary version of this article appeared in ECCC, TR15-005, 2016.