The Taub Faculty of Computer Science Events and Talks

Reed-Muller codes encode an m-variate polynomial of degree r by evaluating it on all points in {0,1}^m. Its distance is 2^{m-r} and so it cannot correct more than that many errors/erasures in the worst case. For random errors one may hope for a better result. In his seminal paper Shannon exactly determined the amount of errors and erasures one can hope to correct for codes of a given rate. Codes that achieve Shannon’s bound are called capacity achieving codes. In this talk we will show that Reed-Muller codes of low rate achieve capacity for both erasures and errors. We will also show that for high rate RM codes achieve capacity for erasures and can handle many more errors than what was previously known.

Based on joint work with Emmanuel Abbe and Avi Wigderson.