A Fourier-Analytic Approach to Reed-Muller Decoding

We present a Fourier-analytic approach to list-decoding Reed-Muller codes over arbitrary finite fields. We use this to show that quadratic forms over any field are locally list-decodeable up to their minimum distance. The analogous statement for linear polynomials was proved in the celebrated works of Goldreich-Levin and Goldreich-Rubinfeld-Sudan. Previously, tight bounds for quadratic polynomials were known only for q = 2 or 3; the best bound known for other fields was the Johnson radius. Departing from previous work on Reed-Muller decoding which relies on some form of self- corrector, our work applies ideas from Fourier analysis of Boolean functions to low-degree polynomials over finite fields, in conjunction with results about the weight- distribution. We believe that the techniques used here could find other applications, we present some applications to testing and learning.