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