Volume 13 (2017)
Article 16 pp. 1-23

Some Limitations of the Sum of Small-Bias Distributions

Received: August 3, 2015

Revised: September 22, 2016

Published: December 14, 2017

Revised: September 22, 2016

Published: December 14, 2017

**Keywords:**complexity theory, pseudorandomness, RL vs. L, error-correcting codes, $k$-wise independence, small-bias distributions, sum of small bias

**Categories:**complexity theory, pseudorandomness, RL vs. L, error-correcting codes, $k$-wise independence, small-bias distribution

**ACM Classification:**F.1.3, G.3, F.2.3

**AMS Classification:**68Q17

**Abstract:**
[Plain Text Version]

$
\newcommand{\cclass}[1]{{\textsf{#1}}}
\newcommand\eps{\varepsilon}
\newcommand\Mod{\mathrm{mod}}
\newcommand\ac{\cclass{AC}}
\newcommand\nc{\cclass{NC}}
\newcommand\ppp{\cclass{P}}
$

We present two approaches to constructing $\eps$-biased distributions $D$ on $n$ bits and functions $f\colon \{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:

- $\eps = 2^{-\Omega(n)}$ and $f$ is in $\ppp$/poly;
- $\eps = 2^{-\Omega(n/\log n)}$ and $f$ is in $\nc^2$;
- $\eps = n^{-c}$ and $f$ is a one-way space $O(c \log n)$ algorithm, for any $c$;
- $\eps = n^{-\Omega(1)}$ and $f$ is a mod 3 linear function.

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.