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-decodable up to their minimum distance. The analogous statement for linear polynomials was proved in the celebrated works of Goldreich Previously, tight bounds for quadratic polynomials were known only for q = 2 and 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.