Rutgers Discrete Mathematics Seminar

Title: Cayley Graphs and List-decodable Zero-rate Codes

Speaker: Noga Alon, Princeton and Tel Aviv UniversityPrinceton

Date: Monday, February 26, 2018 2:00 pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ


What is the maximum possible number of words in a binary code of length n so that there is no Hamming ball of radius (1/4+epsilon)n containing more than two words ? I will show that the answer is Theta(1/epsilon^{3/2}). A crucial ingredient in the proof is a construction of a family of Cayley graphs which is useful in tackling several additional extremal problems in Graph Theory and Geometry. Joint work with Bukh and Polyanskiy.