Combinatorics Seminar

When: Sunday January 14, 10am
Where: Schreiber 309
Speaker: Noga Alon, Tel Aviv University
Title: Cayley graphs and list-decodable zero-rate codes


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+ε)n containing more than two words?

I will show that the answer is Θ(1/ε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.