Fall 2018

Bounded Independence Plus Noise, and the Communication Complexity of Decoding

Monday, October 15th, 2018 3:30 pm4:00 pm

Add to Calendar


Emanuele Viola (Northeastern University)

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.