CAREER: A Theory of Error Correction for Interactive Communication

职业：交互式通信的纠错理论

• 批准号: 1750808
• 负责人: Bernhard Haeupler
• 金额: $ 56万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-02-15 至 2023-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1750808&HistoricalAwards=false
• 关键词: CAREER; Theory; Error; Correction; Interactive

This project aims at developing a theory and methods for correcting errors in interactive communications. Shannon's influential "A Mathematical Theory of Communication" established such a theory for one-way communications. Coding theory has subsequently produced computationally efficient methods for reliable data transmissions over unreliable channels. While error correcting codes have transformed communication technologies over the decades, modern communication settings often go beyond one-way transmissions and instead require many interleaved rounds of interactive communication. The development of interactive equivalents of good error correcting codes for such modern systems is a much harder task, which has attracted attention recently and witnessed encouraging initial successes. This project will further advance the fundamental questions underlying possibilities, limitations, and theoretical underpinnings of reliable interactive communication in the presence of noise, and thus contribute to a solid mathematical and computational theory of reliable interactive communication. The project also has a strong educational component which supports several initiatives to stimulate undergraduates, graduate students, the scientific community, and the general public through education and outreach.The project attacks a diverse set of "classical" questions, such as determining the fundamental communication rate limits for error correction in interactive communications, and explicit constructions of tree codes, a powerful but elusive type of online code. The project also considers the broader context of interactive coding schemes and their wide ranging applicability in other areas of theoretical computer science, including cryptography, privacy, and memory efficient error resilient computations.

该项目旨在开发一种在交互通信中纠正错误的理论和方法。香农颇具影响力的《通信的数学理论》为单向通信建立了这样的理论。编码理论随后产生了用于在不可靠的信道上进行可靠的数据传输的计算高效的方法。虽然纠错码在过去几十年里改变了通信技术，但现代通信设置往往不只是单向传输，而是需要许多交错轮的交互通信。为这样的现代系统开发良好的纠错码的交互等价物是一项困难得多的任务，最近引起了人们的注意，并见证了令人鼓舞的初步成功。这个项目将进一步推进在噪声存在的情况下可靠交互通信的可能性、局限性和理论基础的基本问题，从而有助于建立可靠交互通信的坚实的数学和计算理论。该项目还有一个强大的教育部分，支持通过教育和外展来激励本科生、研究生、科学界和普通公众的几项倡议。该项目解决了一系列不同的经典问题，例如确定交互通信中纠错的基本通信速率限制，以及显式构造树代码，这是一种强大但难以捉摸的在线代码类型。该项目还考虑了交互编码方案的更广泛的背景及其在理论计算机科学的其他领域的广泛适用性，包括密码学、隐私和内存效率高的容错计算。

项目成果

A Time-Optimal Randomized Parallel Algorithm for MIS

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

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

Bridging the Capacity Gap Between Interactive and One-Way Communication

缩小交互式和单向通信之间的能力差距

• DOI: 10.1137/1.9781611974782.138
• 发表时间: 2017
• 期刊: ACM-SIAM Symposium on Discrete Algorithms
• 作者: Haeupler, Bernhard;Velingker, Ameya
• 通讯作者: Velingker, Ameya

Hop-constrained oblivious routing

跳数约束的不经意路由

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