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.
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.
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.
