Locally decodable codes and geometry of tensor norms

Jop Briët , NYU
Fine Hall 224

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 reakthrough 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.