pdf icon
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
Download article from ToC site:
[PDF (301K)] [PS (1603K)] [Source ZIP]
Misc.:
[About the Authors] [HTML Bibliography] [BibTeX]
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:

  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.