The list decoding radius of Reed-Muller codes over small fields
The list decoding radius of Reed-Muller codes over small fields
The list decoding problem for a code asks for the maximal radius up to which any ball of that radius contains only a constant number of codewords. The list decoding radius is not well understood even for well-studied codes, like Reed-Solomon or Reed-Muller codes. The Reed-Muller code F(n,d) for a finite field F is defined by n-variate degree-d polynomials over F. As far as we know, the list decoding radius of Reed-Muller codes can be as large as the minimal distance of the code. This is known in a number of cases: --The Goldreich-Levin theorem and its extensions established it for d=1 (Hadamard codes); --Gopalan, Klivans and Zuckerman established it for the binary field; --and Gopalan established it for d=2 and all fields. In this work (joint with Lovett), we prove the conjecture for all constant prime fields and all constant degrees. In this talk, I will present the proof for our first main theorem which states that the list decoding radius is exactly equal to the minimum distance of the Reed-Muller code for all constant prime fields and constant degrees. For ease of presentation, we will only see the case when d < char(F). The proof relies on several new ingredients, including higher-order Fourier analysis which I will introduce along the way.