Locality in Error-Correcting Codes

纠错码中的局部性

• 批准号: RGPIN-2022-04658
• 负责人: Kopparty, Swastik
• 金额: $ 5.39万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=758683
• 关键词: Locality; 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.

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