CIF: Small: New Coding Techniques for Synchronization Errors

CIF：小：针对同步错误的新编码技术

• 批准号: 1814603
• 负责人: Venkatesan Guruswami
• 金额: $ 47.22万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-10-01 至 2022-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1814603&HistoricalAwards=false
• 关键词: CIF; Small; New; Coding; Techniques

Coding theory has advanced our understanding of how to efficiently correct symbol corruptions and erasures. The error-correcting codes developed by this theory have had a tremendous practical and theoretical impact on technology and engineering as well as mathematics, theoretical computer science, and other fields. Correcting closely related synchronization errors, such as insertions and deletions, however, while also studied since the 1960s, has largely resisted progress so far. The goal of this proposal is to close this gap and develop a better understanding of and new coding techniques for synchronization errors. In addition to resolving fundamental questions on natural and basic error models, the investigators believe that the study has the potential to guide the design of systems which use efficient coding techniques to address synchronization and noise issues jointly, instead of spending significant resources on ensuring very tight controls on synchronization.The project will build on the recent work in this area by the investigators and their students, and investigate new coding approaches for coping with insertions/deletions. For the case of large finite alphabets, the project will investigate codes based on synchronization strings. Synchronization strings isolate and directly tackle the synchronization aspect which distinguishes insertion and deletion errors from symbol corruptions and erasures, yielding an efficient way to reduce them to regular errors. Such a transformation can then leverage the tremendous progress made on regular error-correcting codes toward the design of insertion-deletion codes. The project will also investigate new approaches for the setting of binary or very small alphabets with the goal of better understanding the potential of insertion-deletion codes together with efficient constructions. Beyond simple insertions and deletions, the project will also study more general synchronization error models stemming from practical applications such as tandem repeats or block corruptions. The educational component will infuse appropriate concepts from the project into courses taught by the investigators, and take advantage of the accessible and attractive nature of the topic to engage undergraduates in research, in addition to the substantial involvement of graduate students. The project will aim to forge stronger intellectual ties between the computer science and information theory communities which are both actively engaged in study of codes in various models.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.

编码理论增进了我们对如何有效纠正符号损坏和删除的理解。该理论发展起来的纠错码对技术和工程以及数学、理论计算机科学等领域产生了巨大的实践和理论影响。然而，纠正密切相关的同步错误（例如插入和删除）虽然自 20 世纪 60 年代以来一直在研究，但迄今为止在很大程度上阻碍了进展。该提案的目标是缩小这一差距，并更好地理解同步错误和新的编码技术。除了解决自然和基本误差模型的基本问题外，研究人员认为该研究还有可能指导系统的设计，这些系统使用有效的编码技术来共同解决同步和噪声问题，而不是花费大量资源来确保非常严格的同步和噪声问题。该项目将以研究人员及其学生最近在该领域的工作为基础，并研究处理插入/删除的新编码方法。对于大型有限字母表的情况，该项目将研究基于同步字符串的代码。同步字符串隔离并直接处理同步方面，将插入和删除错误与符号损坏和擦除区分开来，从而产生一种将它们减少为常规错误的有效方法。这样的转换可以利用常规纠错码所取得的巨大进步来设计插入删除码。该项目还将研究设置二进制或非常小的字母的新方法，目的是更好地理解插入删除代码以及高效构造的潜力。除了简单的插入和删除之外，该项目还将研究源自实际应用的更通用的同步错误模型，例如串联重复或块损坏。教育部分将把项目中的适当概念融入到研究人员教授的课程中，并利用该主题的易懂性和吸引力，除了研究生的大量参与之外，还吸引本科生参与研究。该项目旨在在积极从事各种模型中的代码研究的计算机科学和信息理论界之间建立更牢固的智力联系。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值进行评估，被认为值得支持以及更广泛的影响审查标准。

项目成果

Optimal Document Exchange and New Codes for Small Number of Insertions and Deletions

最佳文档交换和少量插入和删除的新代码

• 发表时间: 2019-10
• 期刊: IEEE Symposium on Foundations of Computer Science
• 作者: Haeupler; Bernhard
• 通讯作者: Bernhard

Hop-constrained oblivious routing

跳数约束的不经意路由

• DOI: 10.1145/3406325.3451098
• 发表时间: 2021-06
• 期刊: Symposium on Theory of Computing (STOC
• 作者: Ghaffari, Mohsen;Haeupler, Bernhard;Zuzic, Goran
• 通讯作者: Zuzic, Goran

Synchronization strings: codes for insertions and deletions approaching the singleton bound

同步字符串：接近单例边界的插入和删除代码

• DOI: 10.1145/3055399.3055498
• 发表时间: 2017-10
• 期刊: ACM Symposium on Theory of Computing
• 作者: Haeupler, Bernhard;Shahrasbi, Amirbehshad
• 通讯作者: Shahrasbi, Amirbehshad

Hop-Constrained Expander Decompositions, Oblivious Routing, and Distributed Universal Optimality

跳数约束扩展器分解、不经意路由和分布式通用最优性

• 发表时间: 2022-07
• 期刊: Proceedings of the ACM Symposium on Theory of Computing
• 作者: Haeupler, Bernhard;Räcke, Harald;Ghaffari;Mohsen
• 通讯作者: Mohsen

Round- and Message-Optimal Distributed Graph Algorithms

轮次和消息最优分布式图算法

• DOI: 10.1145/3212734.3212737
• 发表时间: 2018-01
• 期刊: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
• 作者: Haeupler, Bernhard;Hershkowitz, D. Ellis;Wajc, David
• 通讯作者: Wajc, David