In a groundbreaking study, Pravesh Kothari, Visiting Professor (2024) in the School of Mathematics, and Peter Manohar, Member (2024–26) in the School, have transformed theoretical computer scientists’ knowledge of locally correctable codes (LCCs).
A locally correctable code is an error correcting code that contains a self-correction algorithm that can recover, with high probability, any symbol of the original codeword by querying a small number of randomly chosen symbols from a received corrupted codeword. LCCs enable highly efficient procedures for recovering small amounts of data, and have several applications in complexity theory. For instance, they are useful in proving the “hardness” (the difficulty of solving) of problems concerning the approximation of optimization.
Kothari and Manohar were interested in LCCs that have three queries, meaning codes that can correct errors in any single bit of an encoded message by randomly sampling only three positions in the codeword. More specifically, they investigated the “rate,” or redundancy, of these three query LCCs. Redundancy refers to the additional information included in data that is not strictly necessary for conveying the core content, but is nevertheless important for the detection and correction of errors.
For LCCs with two queries, tight exponential lower and upper bounds on their rate have been known for a long time, but in the case of three queries, there was an exponential gap between the known upper and lower bounds. Kothari and Manohar proved an exponential lower bound. In short, they showed that for LCCs with three queries to work effectively, the code must be lengthy. More specifically, it must grow exponentially as the amount of original data increases. The pair’s findings have important implications for complexity theory and various cryptographic applications, including private information retrieval. Their research contributes to our understanding of the fundamental limits of error correction in information transmission and storage.
