Abhishek Bhowmick: The List Decoding Radius of Reed-Muller codes over Small Fields

Abstract: 

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 RM_{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 F_2; and 
Gopalan established it for d=2 and all fields. In a recent work with Lovett, we prove the 
conjecture for all constant prime fields and all constant degrees. The proof relies on several 
new ingredients, including higher-order Fourier analysis.

This is based on joint work with Shachar Lovett