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


Date: Thursday 27th March, 4:30 in Fine Hall 224.
 
Speaker: Jop Briët (NYU)

Title: Locally decodable codes and geometry of tensor norms


Locally decodable codes (LDCs) are error correcting codes that allow 
any single message symbol to be retrieved from a small number 'q' of 
randomly selected codeword symbols. We currently know very little 
about the shortest possible codeword length when 'q' is a constant 
and the message length is allowed to grow. In this talk I will present 
a link between the length of q-LDCs and a geometric property of Banach 
spaces called cotype.

In particular, the existence of short LDCs implies that some of the 
spaces formed by projective tensor products of L_p spaces fail to 
have cotype. As a consequence, we retrieve known optimal lower bounds 
for 2-LDCs from the fact that Schatten-1 space has cotype, and a 
breakthrough 3-LDC construction of Yekhanin and Efremenko implies the 
failure of cotype for the projective tensor product of three copies 
of L_3, answering an open question of Diestel, Fourie and Swart.

Joint work with Assaf Naor and Oded Regev.

                       -----------

Next week: No seminar (conflict with conference). 
Week after: Peter Keevash

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