AF: Small: New Frontiers in Local Error-Correction

现代通信和数据存储技术使用数学纠错码来处理物理设备的噪声和不可靠性。该项目将开发新的纠错码，支持“本地”算法进行错误检测和纠错：这些算法以超快的速度提供强大的纠错保证。该项目开发的纠错代码和算法将有可能应用于现实世界的数据存储应用，这与当前的云计算技术非常相关。这个项目的教育部分将包括指导和教育打算从事自己研究事业的初级研究人员，包括妇女和少数民族。该项目还将开发有关相关主题的重要进展的课程，并将课程材料公开。在技术层面，本项目研究了局部纠错码的存在与构造、算法和基本限制等主要问题。本地纠错码是支持次线性时间错误检测和/或纠错的纠错码的现代版本。在过去的几十年里，它们在理论计算机科学中变得越来越重要，这既是因为它们在通信和数据存储方面的潜在应用，也是因为它们与复杂性理论、伪随机性和密码学的联系。该项目将开发新的代数、概率和算法工具来设计和推理这些代码，以及更普遍的局部算法。该项目的动机是研究者最近取得的几项进展，例如构建新的高速率纠错码，首次允许次多项式时间纠错和错误检测，以及首次构建常数速率的概率可检查证明，可在次线性时间内进行检查。这些进步极大地改变了这一领域的可能性，并有可能极大地改变数据中心存储数据的方式。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Modern communication and data storage technologies use mathematical error-correcting codes to cope with noise and unreliability of physical devices. This project will develop new error-correcting codes which support "local" algorithms for error-detection and error-correction: these give strong error-correction guarantees at ultra-fast speeds. The error-correcting codes and algorithms developed in this project will have the potential be applied to real-world data storage applications, which is very relevant to current cloud computing technology. The educational component of this project will involve the mentoring and education of junior researchers who intend to pursue their own careers in research, including women and minorities. This project will also develop courses about the important advances in the relevant topics, and make the course materials publicly available.At the technical level, this project investigates the main problems on the existence and construction of, and algorithms and fundamental limits for local error-correcting codes. Local error-correcting codes are modern versions of error-correcting codes that support sublinear-time error detection and/or correction. They have gained increasing importance in theoretical computer science over the last few decades, both because of potential applications to communication and data storage, as well as connections to complexity theory, pseudorandomness, and cryptography. This project will develop new algebraic, probabilistic and algorithmic tools to design and reason about such codes, and local algorithms more generally. This project is motivated by several recent advances made by the investigator, such as 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. These advances have significantly altered what is believed to be possible in this domain, and have the potential to dramatically change the way data is stored in data centers.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.