EE Seminar: Reed-Muller codes for random errors and erasures

~~(The talk will be given in English)

Prof. Amir Shpilka
CS, Tel Aviv University
Monday, May 4th, 2015
15:00 - 16:00
Room 011, Kitot Bldg., Faculty of Engineering
Reed-Muller codes for random errors and erasures
Abstract

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 joint works with Emmanuel Abbe and Avi Wigderson and with Ramprasad saptharishi and Ben lee Volk.