DIMACS Theoretical Computer Science Seminar

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


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/