Title: Locally Decodable Codes and Banach-space Geometry
Speaker: Jop Briet, NYU
Date: Wednesday, October 29, 2014 11:00-12:00pm
Location: CoRE Bldg, Room 301A, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
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)
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S14/