Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
List-decoding Reed-Muller codes over small fields

Parikshit Gopalan, Adam R. Klivans, and David Zuckerman

Abstract

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.

Details

Publication typeInproceedings
Published inSTOC'08
PublisherACM
> Publications > List-decoding Reed-Muller codes over small fields