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.