The Taub Faculty of Computer Science Events and Talks

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.