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