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 for degree $2$. Previously, tight bounds for quadratic polynomials were known only for $q =2,3$; the best bound known for other fields was the Johnson radius which is roughly $1 - 1/\sqrt{q}$.

We say that a polynomial over $\F_q$ is $k$-dimensional if it can be expressed as a function of $k$ linear functions. We reduce the Reed-Muller list-decoding problem to list-decoding low-dimensional polynomials and present a new Fourier-based algorithm for the low-dimensional case. The list-decoding radius achieved by this approach for degree $3$ and higher depends on questions regarding the weight-distribution of the Reed-Muller code. We propose a conjecture in this regard, which if true, improves on the best known bounds for the list-decoding radius for all $d$ and $q$. The conjecture holds true for $\F_2$, giving an alternate proof of the main result of GKZ.

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. We believe that the techniques used here could find other applications, we present applications to testing and learning.