Locality in Error-Correcting Codes

点击翻译按钮获取中文摘要

This project investigates the main problems on the existence, construction, algorithms and limitations for *local* error-correcting codes, as well as their implications across theoretical computer science. Error-correcting codes give a way of formatting data so as to make it robust to errors. Local error-correcting codes are error-correcting codes with rich local structure, enabling super-fast detection and correction of errors. Apart from their natural applications to data storage and communication, they form the combinatorial core of Probabilistically Checkable Proofs for NP, and they underlie a number of breakthroughs in complexity theory, cryptography and pseudorandomness over the past three decades. This project is motivated by number of recent advances by the PI, significantly deepening our understanding of local error-correcting codes, and exposing a wide range of new questions and possibilities. Some of these advances include the construction of new high rate error-correcting codes allowing, for the first time, subpolynomial-time error-correction and error-detection, and the first constructions of Probabilistically Checkable Proofs of constant rate, checkable in sublinear time. The algebraic and probabalistic tools developed along the way enabled other advances by the PI in related fields, such as a new FFT-like algorithm based on elliptic curves, leading to the asymptotically fastest univariate polynomial interpolation algorithm for a general finite field, and the first list-decodable and locally list-decodable codes with constant list size and constant alphabet size. The main goal of this project is to understand the fundamental tradeoffs between locality, redundancy of encoding and robustness to errors that local error-correcting codes have. The tantalizing message of the previously mentioned results is that, as far as we know, locality can come for *free*; this project aims to get to the bottom of this, potentially resolving central questions about codes and Probabilistically Checkable Proofs. In addition, the project will investigate implications of this newly found understanding of local codes for other areas across theoretical computer science. Finally, this project will develop algebraic, probabilistic and algorithmic methods for reasoning about locality and information. Along the way, this project will explore other closely related directions, such as the development of fast algebraic algorithms and applications of coding to pseudorandomness and complexity theory.