A Fourier-analytic approach to Reed-Muller decoding

  • Parikshit Gopalan

FOCS 2010 |

Published by IEEE

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.