***********************************
                * Princeton Discrete Math Seminar *
                ***********************************


Date: Thursday 9th April, 3:00 in Fine Hall 224.
 
Speaker: Abhishek Bhowmick (U.Texas Austin)

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


                       -----------

Next week: Ori Parzanchevski 

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)