CS Events

Locally decodable codes are error-correcting codes that admit efficient decoding algorithms: They give a method to encode k bit messages into n bit codewords such that even after a constant fraction of the bits of the codeword get corrupted, any bit of the original message can be recovered by only looking at a sublinear number of bits (or in some cases even a constant number of bits) of the corrupted codeword. The tradeoff between the rate of a code (i.e., the ratio k/n) and the locality/efficiency of its decoding algorithms has been studied extensively in the past couple of decades with numerous applications to theoretical computer science, and more recently to practical data storage and retrieval.

In this talk I will survey some recent and not-so-recent results (both constructions and lower bounds) for locally decodable codes. In particular I will focus on some recent results that gave the first codes of high rate that are also efficiently locally decodeable. I will also highlight some of the most interesting challenges that remain.

This is based on joint works with Swastik Kopparty, Or Meir, Noga Ron-Zewi, Sergey Yekhanin.