List-decoding Reed-Muller codes over small fields

Parikshit Gopalan, Adam R. Klivans, and David Zuckerman
May 2008

We give the first local list-decoding algorithm for binary Reed-Muller codes. Our algorithms work up to the list-decoding radius of the code. We show that this radius exceeds the Johnson bound and is in fact the minimum distance of the code.

We conjecture a similar statement holds for all (non-binary) fields, and prove this in some special cases.