Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

Coding Theory: Reed-Muller Codes for Random Erasures and Errors
event speaker icon
Amir Shpilka (Tel-Aviv University)
event date icon
Sunday, 20.03.2016, 14:30
event location icon
Taub 601
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.