CRII: CIF: Locality in Error Correcting Codes: Fundamental Trade-Offs

这个项目研究了纠错码中围绕局部性的基本权衡。在纠错码中，“局部性”指的是量化从编码数据中恢复少量信息的容易程度的几种方法。局部性的概念几乎与编码理论本身一样长，今天，对纠错码局部性的研究对于从理论（复杂性理论）到实际（分布式存储方案）的应用都是至关重要的。这项研究提高了我们对局部性的基本科学认识，并在这些应用方面取得了进展。除了它的科学影响，这个项目有更广泛的教育影响，通过开发课程材料和提供机会，研究生和本科生的研究。这项研究的方法是弥合两种不同文献之间的差距。在理论计算机科学中，局部可解码码和局部可纠错码的研究已经进行了超过15年，并与复杂性理论和密码学中的许多基本问题联系在一起。在过去的五年中，局部性的研究在分布式存储中也开始兴起，其形式是局部可恢复代码和相关概念。这两条研究线在不同的参数体系下运行，并受到不同应用的激励。目前的研究通过研究中间参数体系将两者联系在一起，并探索了围绕局部性的基本数学权衡。通过扩展我们对编码理论中局部性的理解，本研究可以在编码、复杂性理论、密码学和分布式存储等领域的重要问题上取得进展；它还发展了一种理论，可以找到更多的应用前景。

This project investigates the fundamental trade-offs surrounding locality in error correcting codes. In error correcting codes, "locality" refers to several ways of quantifying how easily a small amount of information can be recovered from encoded data. Notions of locality have been around almost as long as coding theory itself, and today the study of locality in error correcting codes is fundamental to applications ranging from the very theoretical (complexity theory) to the very practical (distributed storage schemes). This research improves our basic scientific understanding of locality, and in doing so it makes progress on these applications. Beyond its scientific impact, this project has broader educational impact, through the development of course materials and by providing opportunities for graduate and undergraduate research.The approach of this research is to bridge a gap between two different bodies of literature. In Theoretical Computer Science, Locally Decodable and Locally Correctable Codes have been studied for over 15 years, and have been linked to many fundamental problems in complexity theory and cryptography. In the past five years, the study of locality has also taken off in distributed storage, in the form of Locally Recoverable Codes and related notions. These two lines of research operate in different parameter regimes and are motivated by different applications. The current research ties the two together by studying intermediate parameter regimes, and explores the fundamental mathematical trade-offs surrounding locality. By extending our understanding of locality in coding theory, this research can make progress on important problems in coding, complexity theory, cryptography, and distributed storage; it also develops a theory which could find many more applications going forward.