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.

编码理论提出了我们对如何有效纠正符号腐败和擦除的理解。该理论开发的错误校正代码对技术和工程以及数学，理论计算机科学和其他领域产生了巨大的实用和理论影响。然而，纠正密切相关的同步误差，例如插入和缺失，尽管自1960年代以来也进行了研究，但迄今已在很大程度上抵制了进展。该提案的目的是缩小这一差距，并对同步错误有更好的理解和新的编码技术。除了解决自然和基本错误模型上的基本问题外，研究人员还认为，该研究有可能指导系统的设计，这些系统使用有效的编码技术共同解决了同步和噪声问题，而不是花费大量资源来确保对同步的非常紧张的控制。对于大有限字母，该项目将根据同步字符串研究代码。同步字符串隔离并直接应对同步方面，该方面将插入和删除错误与符号损坏和擦除区分开，从而产生了一种有效的方法来将它们减少到常规错误。然后，这种转换可以利用常规误差校正代码在插入删除代码设计上取得的巨大进展。该项目还将研究设置二进制或非常小的字母的新方法，以便更好地了解插入损坏代码的潜力以及有效的结构。除了简单的插入和删除外，该项目还将研究由实际应用（例如串联重复或阻止腐败）引起的更通用的同步错误模型。教育组成部分将把项目从项目的课程中注入适当的概念，并利用该主题的可访问性和吸引力的性质，除了研究生的实质性参与外，还可以参与研究。该项目将旨在在计算机科学与信息理论社区之间建立更牢固的智力联系，这些社区都积极参与各种模型中的守则研究。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的智力优点和更广泛影响的审查标准通过评估来支持的。

项目成果

Coding Against Deletions in Oblivious and Online Models

在遗忘模型和在线模型中针对删除进行编码

• DOI: 10.1109/tit.2020.2968298
• 发表时间: 2020
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Guruswami, Venkatesan;Li, Ray
• 通讯作者: Li, Ray

Rate-Distance Trade-offs for List-Decodable Insertion-Deletion Codes

• DOI: 10.1109/itw54588.2022.9965935
• 发表时间: 2020-09
• 期刊: 2022 IEEE Information Theory Workshop (ITW)
• 作者: Bernhard Haeupler;Amirbehshad Shahrasbi

Round- and Message-Optimal Distributed Graph Algorithms

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

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

A Time-Optimal Randomized Parallel Algorithm for MIS

• DOI: 10.1137/1.9781611976465.172
• 发表时间: 2021-01
• 作者: M. Ghaffari;Bernhard Haeupler

Online Matching with General Arrivals

• DOI: 10.1109/focs.2019.00011
• 发表时间: 2019-01-01
• 期刊: 2019 IEEE 60TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2019)
• 作者: Gamlath, Buddhima;Kapralov, Michael;Wajc, David
• 通讯作者: Wajc, David