Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR15-005 | 10th March 2016 16:12

#### Some limitations of the sum of small-bias distributions

Revision #1
Authors: Chin Ho Lee, Emanuele Viola
Accepted on: 10th March 2016 16:12
Keywords:

Abstract:

We exhibit $\epsilon$-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$, for any of the
following choices:

1. $\epsilon = 2^{-\Omega(n)}$ and $f$ is in P/poly;

2. $\epsilon = 2^{-\Omega(n/\log n)}$ and $f$ is in NC$^2$;

3. $\epsilon = n^{-\log^{\Omega(1)} n}$ and $f$ is in AC$^0$;

4. $\epsilon = n^{-c}$ and $f$ is a one-way space $O(c \log n)$ algorithm, for any $c$;

5. $\epsilon = n^{-0.029}$ 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 $\epsilon$.

Meka and Zuckerman (RANDOM 2009) prove 5 with $\epsilon = O(1)$. Bogdanov, Dvir, Verbin, and Yehudayoff (Theory Of
Computing 2013) prove 2 with $\epsilon = 2^{-O(\sqrt{n})}$. Chen
and Zuckerman (personal communication) give an alternative
proof of 4.

1-4 are obtained via a new and simple connection
between small-bias distributions and error-correcting
codes. We also give a conditional result for DNF
formulas, and show that $5$-wise independence
does not hit mod $3$ linear functions.

Changes to previous version:

The previous version made an unconditional claim about AC^0. But the proof had a gap. We do not know that the claim is false. But this version does not make it.

### Paper:

TR15-005 | 5th January 2015 14:46

#### Some limitations of the sum of small-bias distributions

TR15-005
Authors: Chin Ho Lee, Emanuele Viola
Publication: 5th January 2015 14:46
Keywords:

Abstract:

We exhibit $\epsilon$-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$, for any of the
following choices:

1. $\epsilon = 2^{-\Omega(n)}$ and $f$ is in P/poly;

2. $\epsilon = 2^{-\Omega(n/\log n)}$ and $f$ is in NC$^2$;

3. $\epsilon = n^{-\log^{\Omega(1)} n}$ and $f$ is in AC$^0$;

4. $\epsilon = n^{-c}$ and $f$ is a one-way space $O(c \log n)$ algorithm, for any $c$;

5. $\epsilon = n^{-0.029}$ 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 $\epsilon$.

Meka and Zuckerman (RANDOM 2009) prove 5 with $\epsilon = O(1)$. Bogdanov, Dvir, Verbin, and Yehudayoff (Theory Of
Computing 2013) prove 2 with $\epsilon = 2^{-O(\sqrt{n})}$. Chen
and Zuckerman (personal communication) give an alternative
proof of 4.

1-4 are obtained via a new and simple connection
between small-bias distributions and error-correcting
codes. We also give a conditional result for DNF
formulas, and show that $5$-wise independence
does not hit mod $3$ linear functions.

ISSN 1433-8092 | Imprint