ECCC-Report TR15-005https://eccc.weizmann.ac.il/report/2015/005Comments and Revisions published for TR15-005en-usThu, 10 Mar 2016 16:12:53 +0200
Revision 1
| Some limitations of the sum of small-bias distributions |
Emanuele Viola,
Chin Ho Lee
https://eccc.weizmann.ac.il/report/2015/005#revision1We 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.Thu, 10 Mar 2016 16:12:53 +0200https://eccc.weizmann.ac.il/report/2015/005#revision1
Paper TR15-005
| Some limitations of the sum of small-bias distributions |
Emanuele Viola,
Chin Ho Lee
https://eccc.weizmann.ac.il/report/2015/005We 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.Mon, 05 Jan 2015 14:46:25 +0200https://eccc.weizmann.ac.il/report/2015/005