Speaker: Shachar Lovett, University of California, San Diego

Title: List decoding 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.

Fix a prime finite field F. The Reed-Muller code RM_F(n,d) is defined by n-variate degree-d polynomials over F. In this work, we study the list decoding radius of Reed-Muller codes over a constant prime field F=F_p, constant degree d and large n.We show that the list decoding radius is equal to the minimal distance of the code. This resolves a conjecture of Gopalan-Klivans Zuckerman [STOC 2008], who among other results proved it in the special case of F=F_2; and extends the work of Gopalan [FOCS 2010] who proved the conjecture in the case of d=2. We also give tight bounds on the number of codewords in radii exceeding the list decoding radius. This extends the work of Kaufman-Lovett-Porat [IEEE Inf. Theory 2012] who provedsimilar bounds over F_2.

The proof relies on several new ingredients: an extension of the Frieze-Kannan weak regularity to general function spaces, higher-order Fourier analysis, and an extension of the Schwarz-Zippel lemma to compositions of polynomials.

Joint work with Abhishek Bhowmick.