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

Abstract:

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.