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

Some Limitations of the Sum of Small-Bias Distributions

by Chin Ho Lee and Emanuele Viola

Received: August 3, 2015
Revised: September 22, 2016
Published: December 14, 2017

$ \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:

1. $\eps = 2^{-\Omega(n)}$ and $f$ is in $\ppp$/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.

DOI: 10.4086/toc.2017.v013a016

© 2017 Chin Ho Lee and Emanuele Viola
Licensed under a Creative Commons Attribution License (CC-BY)