Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Some limitations of the sum of small-bias distributions

RSS-Feed




Revision #1
Authors: Chin Ho Lee, Emanuele Viola
Accepted on: 10th March 2016 16:12
Downloads: 951
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
Downloads: 1681
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