Amir Shpilka: Reed-Muller Codes for Random Erasures and Errors

Wednesday, September 30, 2015 - 4:00pm to 5:00pm
Amir Shpilka
Tel Aviv University

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. Time permitting we will give an algorithm that for high rate RM codes corrects many more random errors than what minimal distance dictates.


Based on work with Emmanuel Abbe and Avi Wigderson and with Ramprasad Saptharishi and Ben lee Volk.