Overview

Any application that either stores or transmits data has to deal with errors. Classical coding theory tells us how to encode data efficiently so that we can recover every single bit of data even if 10% of the stored information is lost. A caveat with this guarantee is that typically one needs to read the entire codeword to recover even a single bit of data. Is this shortcoming inherent? This is the question that research on locally decodable codes seeks to answer.

Locally decodable codes (LDCs) are error-correcting codes with ultra-efficient decoding algorithms, which can recover any symbol of the data by reading a tiny fraction of the codeword. In an LDC, the number of read opeartions is tied to the amount of data symbols we wish to reconstruct, and not the total amount of data that is being stored which could be several orders of magnitude larger. In addition to being natural and useful objects in their own right, such codes have applications to cryptography and privacy.

Our theoretical research aims to design better LDCs and decoders for them. It has resulted in the first non-trivial LDCs which read only 3 bits of the codeword to recover each bit of data, and the first linear rate codes with sub-linear decoding algorithms. It has also resulted in the best known decoding algorithms for important codes such as Reed-Muller and tensored Reed Solomon codes.

A practical goal of our research is to use these insights to design better coding schemes for actual storage and transmission systems. The hope is to match the ease of recovery of simple duplication schemes with the fault tolerance of more sophiticated schemes.