We present two approaches to constructing $eps$-biased distributions$D$ on $n$ bits and functions $fcolon {0,1}^n o {0,1}$ suchthat the XOR of two independent copies ($D+D$) does not fool $f$.Using them, we give constructions forany of the following choices: $eps = 2^{-Omega(n)}$ and $f$ is in $ppp$/poly; $eps = 2^{-Omega(n/log n)}$ and $f$ is in $c^2$; $eps = n^{-c}$ and $f$ is a one-way space $O(c log n)$ algorithm, for any $c$; $eps = n^{-Omega(1)}$ and $f$ is a mod 3 linear function.All the results give one-sided distinguishers, and extend to theXOR of more copies for suitable $eps$. We also giveconditional results for $c^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 inECCC, TR15-005, 2016.
展开▼
机译：我们提出了两种在$ n $位上构造$ eps $有偏分布$ D $和函数$ f colon {0,1 } ^ n to {0,1 } $的方法，使得XOR为两个独立的副本（$ D + D $）不会欺骗$ f $。使用它们，我们可以为以下任何一种选择构造：$ eps = 2 ^ {- Omega（n）} $并且$ f $在$ ppp $ / poly; $ eps = 2 ^ {- Omega（n / log n）} $和$ f $在$ nc ^ 2 $中; $ eps = n ^ {-c} $并且$ f $是单向空间$ O（c log n）$算法，对于任何$ c $; $ eps = n ^ {- Omega（1）} $和$ f $是mod 3线性函数。所有结果给出了单侧区分符，并扩展为适用于$ eps $的更多副本的XOR。我们还给出了$ ac ^ 0 $和DNF公式的条件结果.Meka和Zuckerman（RANDOM 2009）用$ eps = O（1）$证明4.Bogdanov，Dvir，Verbin和Yehudayoff（计算理论，2013）用$ eps = 2 ^ {-O（ sqrt {n}）} $证明2。 Chen和Zuckerman（个人通讯）提供了3.的替代证明。本文的初步版本出现在ECCC，TR15-005,2016年。
展开▼
