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

CRII：CIF：纠错码的局部性：基本权衡

基本信息

批准号：
1657049
负责人：
Mary Wootters
金额：
$ 17.5万
依托单位：
Stanford University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-02-15 至 2019-01-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1657049&HistoricalAwards=false
关键词：
CRII CIF Locality Error Correcting

项目摘要

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.

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

项目成果

期刊论文数量（4）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Local List Recovery of High-Rate Tensor Codes & Applications

高速张量代码的本地列表恢复

DOI：
10.1109/focs.2017.27
发表时间：
2017-10
期刊：
58th Annual IEEE Symposium on Foundations of Computer Science
影响因子：
0
作者：
Hemenway, Brett;Ron;Wootters, Mary
通讯作者：
Wootters, Mary

Limitations of piggybacking codes with low substriping

低子带化的捎带代码的局限性

DOI：
10.1109/allerton.2017.8262864
发表时间：
2017-10-01
期刊：
2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton)
影响因子：
0
作者：
Reyna Hulett;Mary Wootters
通讯作者：
Mary Wootters

Locality via Partially Lifted Codes

通过部分提升代码的局部性