A crash course on locally decodable codes
Amit Deshpande
MIT, USA.
24-08-07

---

Abstract

Locally decodable codes (LDCs) are error-correcting codes such that one can find any bit of the original message by looking only at a small part of the received word. In this talk, we will glimpse at the bigger picture through the works of Katz-Trevisan, Goldreich-Karloff-Schulman-Trevisan, Yekhanin, Woodruff, and others. I promise to give you many proofs, open problems, hypergraphs and hypercubes. I ask for your questions in return.