Abstract
We show that if we add a little noise to any distribution with bounded independence then we fool tests given by the product of bounded functions. This result has applications to pseudorandomness and communication complexity. In the talk we shall consider decoding noisy codewords of length m split among k parties. For Reed-Solomon codes of dimension m/k where k = O(1), communication Omega(pm) is required to decode one message symbol from a codeword with pm errors, and this is nearly tight. This result gives a formal sense in which decoding is harder than encoding. Based on work with Elad Haramaty and Chin Ho Lee.