List-decoding Reed-Muller codes over small fields

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.

proc.pdf
PDF file
rm-full-July 2011.pdf
PDF file

In  STOC'08

Publisher  ACM

Details

TypeInproceedings
> Publications > List-decoding Reed-Muller codes over small fields