Please help us improve your experience by sending us a comment, question or concern
Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.
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 [GL89] and Goldreich-Rubinfeld-Sudan [GRS00]. Previously,
tight bounds for quadratic polynomials were known only for q = 2; 3 [GKZ08]; the best bound known for other fields was the Johnson radius.
Our approach departs from previous work on Reed-Muller decoding which relies on some form of self-correction [GRS00, AS03, STV01, GKZ08]. We seek to explain the good list-decoding properties of RM codes by using the rich structure in the weight distribution of these codes. We observe that the crux of the problem is to bound the number of low-weight codewords near a received word. We do this by applying ideas from Fourier analysis of Boolean functions to low-degree polynomials over finite fields, in conjunction with classical results about the structure of low-weight codewords.