Locality in Error-Correcting Codes

这个项目调查了关于本地纠错码的存在、构造、算法和限制的主要问题，以及它们在理论计算机科学中的影响。纠错码提供了一种格式化数据的方法，以使其对错误具有健壮性。局部纠错码是具有丰富局部结构的纠错码，能够超快地检测和纠正错误。除了它们在数据存储和通信方面的自然应用外，它们还构成了NP的概率可检验证明的组合核心，并且它们是过去三十年来复杂性理论、密码学和伪随机性的一些突破的基础。这个项目的动机是PI最近取得的一些进展，显著加深了我们对本地纠错码的理解，并暴露了一系列新的问题和可能性。其中一些进展包括构造新的高速率纠错码，首次允许亚多项式时间纠错和检错，以及第一次构造恒定速率的概率可检验的证明，可在次线性时间检验。随着代数和概率论工具的发展，PI在相关领域取得了其他进展，例如基于椭圆曲线的新的类似FFT的算法，导致了用于一般有限域的渐近最快的单变量多项式插值算法，以及第一个列表可解码和局部列表可解码的恒定列表大小和恒定字母表大小的代码。这个项目的主要目标是了解本地纠错码在局部性、编码冗余性和对错误的稳健性之间的基本权衡。前面提到的结果的诱人信息是，据我们所知，局部性可以免费提供；这个项目的目标是找出这个问题的真相，潜在地解决关于代码和概率可核查证据的核心问题。此外，该项目将调查这种新发现的对当地规范的理解对理论计算机科学中其他领域的影响。最后，这个项目将开发关于位置和信息的推理的代数、概率和算法方法。在此过程中，该项目还将探索其他密切相关的方向，例如快速代数算法的开发以及编码对伪随机性和复杂性理论的应用。

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.