Theory Seminar: Decoding Reed-Muller Codes from Many Random Errors

Ben Lee Volk (Tel-Aviv University)
Wednesday, 24.6.2015, 12:30
Taub 201

Reed-Muller codes encode an m-variate polynomial of degree r by its evaluations over all points in {0,1}^m. The distance of the code is 2^{m-r}, so in the worst case it is impossible to correct more that half that number of errors. For the model of random errors, however, one may hope to achieve better parameters.

In this talk we will show an efficient algorithm to correct (roughly) m^{(m-r)/2} random errors for certain ranges of r (coding-theoretic conjectures suggest that the algorithm in fact works for any degree). The algorithm is based on solving a carefully designed set of linear equations and thus it is different from known algorithms for decoding Reed-Muller codes.

Based on a joint work with Ramprasad Saptharishi and Amir Shpilka.

Back to the index of events