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

本计画探讨错误更正码中局部性的基本权衡。 在纠错码中，“局部性”是指量化从编码数据中恢复少量信息的容易程度的几种方法。 局部性的概念几乎和编码理论本身一样长，今天纠错码中局部性的研究对于从非常理论的（复杂性理论）到非常实用的（分布式存储方案）的应用都是基础。 这项研究提高了我们对局部性的基本科学理解，并在此过程中在这些应用方面取得了进展。 除了其科学影响，该项目具有更广泛的教育影响，通过课程材料的开发，并通过提供研究生和本科生research.Approach研究的机会是弥合两个不同的文学机构之间的差距。 在理论计算机科学中，局部可解码和局部可纠正码已经研究了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.