A Fourier-Analytic Approach to Reed-Muller Decoding
Parikshit Gopalan · IEEE Transactions on Information Theory · 2010
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 GoldreichPreviously, 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.