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

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Decoding Reed-Muller Codes from Many Random Errors
event speaker icon
Ben Lee Volk (Tel-Aviv University)
event date icon
Wednesday, 24.06.2015, 12:30
event location icon
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.