AF: Small: New Frontiers in Local Error-Correction

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

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.