A Fourier-analytic approach to Reed-Muller decoding

Parikshit Gopalan

Abstract

We present a Fourier-analytic approach to list-decoding Reed-Muller codes over arbitrary finite fields. We prove that the list-decoding radius for quadratic polynomials equals 1-2/q over any field Fq where q > 2. This confirms a conjecture due to Gopalan, Klivans and Zuckerman [GKZ08] for degree 2.

Details

Publication typeInproceedings
Published inFOCS 2010
PublisherIEEE
> Publications > A Fourier-analytic approach to Reed-Muller decoding