摘要：We present two approaches to constructing εε-biased distributions DD on nn bits and functions f:{0,1}n→{0,1}f:{0,1}n→{0,1} such that the XOR of two independent copies (D+DD+D) does not fool ff. Using them, we give constructions for any of the following choices:ε=2−Ω(n)ε=2−Ω(n) and ff is in PP/poly;ε=2−Ω(n/logn)ε=2−Ω(n/logn) and ff is in NC2NC2;ε=n−cε=n−c and ff is a one-way space O(clogn)O(clogn) algorithm, for any cc;ε=n−Ω(1)ε=n−Ω(1) and ff is a mod 3 linear function.All the results give one-sided distinguishers, and extend to the XOR of more copies for suitable εε. We also give conditional results for AC0AC0 and DNF formulas.Meka and Zuckerman (RANDOM 2009) prove 4 with ε=O(1)ε=O(1). Bogdanov, Dvir, Verbin, and Yehudayoff (Theory of Computing, 2013) prove 2 with ε=2−O(n√)ε=2−O(n). Chen and Zuckerman (personal communication) give an alternative proof of 3.
关键词：complexity theory; pseudorandomness; RL vs. L; error-correcting codes; kk-wise independence; small-bias distributions; sum of small bias
