New Approaches to Constructing Locally Decodable Codes

Locally-decodable codes are error-correcting codes that have a local-decodability property: any bit of the underlying message can be recovered (with high probability) by reading only a small number of symbols of the corrupted codeword. Asymptotically, the most efficient locally-decodable codes are the "matching-vector" codes introduced by Efremenko in 2009.

In this talk we will examine two recent works that provide new general approaches to constructing efficient locally-decodable codes. Both techniques a generalization of existing techniques and provide significantly more intuitive constructions. The first, uses a connection to secure multiparty computation. By viewing locally-decodable codes as a special case of secure multiparty computation, many existing constructions (including Efremenko's matching vector codes) can be cast as problems in secure MPC, and existing constructions can be simplified and improved. The second, takes a more mathematical view, and shows that locally-decodable codes arise from certain group representations. Both techniques provide
elegant frameworks for thinking about the problem of constructing efficient locally decodable codes.

Share Conversion and Private Information Retrieval, Beimel, Ishai, Kushilevitz, Orlov CCC

From Irreducible Representations to Locally Decodable Codes, Klim Efremenko STOC