We exhibit -biased distributions D on n bits and functions f : 0 1 n 0 1 such that the xor of two independent copies ( D + D ) does not fool f , for any of the following choices:1. = 2 ? ( n ) and f is in P/poly;2. = 2 ? ( n log n ) and f is in NC 2 ;3. = n ? log (1) n and f is in AC 0 ;4. = n ? c and f is a one-way space O ( c log n ) algorithm, for any c ;5. = 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 .Meka and Zuckerman (RANDOM 2009) prove 5 with = O (1) . Bogdanov, Dvir, Verbin, and Yehudayoff (Theory Of Computing 2013) prove 2 with = 2 ? O ( 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.
展开▼
