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

Speaker: Noga Alon (Princeton)

Thursday 8th February, 3:00 in Fine Hall 224.
 
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+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.

		------------------------------------

Next week: Bhargav Narayanan

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