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 F_q where q > 2. This confirms a conjecture due to Gopalan, Klivans and Zuckerman [GKZ08] for degree 2.

PDF file

Details