Let D be a b -wise independent distribution over 0 1 m . Let E be the ``noise'' distribution over 0 1 m where the bits are independent and each bit is 1 with probability 2 . We study which tests f : 0 1 m [ − 1 1 ] are \e -fooled by D + E , i.e., \E [ f ( D + E )] − \E [ f ( U )] \e where U is the uniform distribution. We show that D + E \e -fools product tests f : ( 0 1 n ) k [ − 1 1 ] given by the product of k bounded functions on disjoint n -bit inputs with error \e = k (1 − ) ( b 2 m ) , where m = n k and b n . This bound is tight when b = ( m ) and ( log k ) m . For b m 2 3 log m and any constant the distribution D + E also 0 1 -fools log-space algorithms.

We develop two applications of this type of results. First, we prove communication lower bounds for decoding noisy codewords of length m split among k parties. For Reed--Solomon codes of dimension m k where k = O (1) , communication ( m ) − O ( log m ) is required to decode one message symbol from a codeword with m errors, and communication O ( m log m ) suffices. Second, we obtain pseudorandom generators. We can \e -fool product tests f : ( 0 1 n ) k [ − 1 1 ] under any permutation of the bits with seed lengths 2 n + O ( k 2 log (1 \e )) and O ( n ) + O ( n k log 1 \e ) . Previous generators had seed lengths n k 2 or n n k .