Locally decodable codes (LDCs) are error correcting codes that allow any symbol of an encoded message to be retrieved by querying only a small number of randomly selected codeword symbols, even if the codeword is partially corrupted. A main open problem is to determine what the smallest-possible codeword length of such codes is when the query complexity is a fixed constant. This talk is about a link between this problem and basic properties of certain Banach spaces that has implications in two directions. In one direction the link gives a short alternative proof of the known exponential lower bound on the length of binary 2-query LDCs due to Kerenidis and de Wolf ('04). In the other direction it shows that the known existence of sub-exponential-length 3-query LDCs implies the answer to an open question about the geometry of tensor products of l_p spaces.

(Based on joint work with Assaf Naor and Oded Regev)