Cayley graphs and list-decodable zero-rate codes

Cayley graphs and list-decodable zero-rate codes

-
Noga Alon, Princeton University
Fine Hall 224

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.