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.

该项目旨在开发一种理论和方法，以纠正交互式通信中的错误。香农的有影响力的“交流数学理论”为单向通信建立了这样的理论。随后，编码理论为不可靠的通道上的可靠数据传输产生了计算有效的方法。尽管错误纠正代码在数十年中已经改变了通信技术，但现代通信设置通常超出了单向传输，而需要许多相互交流的交互式交流。纠正此类现代系统的良好错误代码的交互式等效的发展是一项更加困难的任务，最近引起了人们的注意，并见证了最初的成功。该项目将进一步推进可靠的互动交流的基本问题，局限性和理论基础，并在存在噪声的情况下，从而有助于可靠的交互式交流的坚实数学和计算理论。 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.该项目还考虑了交互式编码方案的更广泛背景及其在理论计算机科学其他领域的广泛适用性，包括密码学，隐私和内存有效的错误弹性计算。

项目成果

期刊论文数量（45）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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

DOI：
10.1109/itw54588.2022.9965935
发表时间：
2020-09
期刊：
2022 IEEE Information Theory Workshop (ITW)
影响因子：
0
作者：
Bernhard Haeupler;Amirbehshad Shahrasbi
通讯作者：
Bernhard Haeupler;Amirbehshad Shahrasbi

Hop-constrained oblivious routing

跳数约束的不经意路由

DOI：
10.1145/3406325.3451098
发表时间：
2021
期刊：
Symposium on Theory of Computing (STOC
影响因子：
0
作者：
Ghaffari, Mohsen;Haeupler, Bernhard;Zuzic, Goran
通讯作者：
Zuzic, Goran

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)
影响因子：
0
作者：
Gamlath, Buddhima;Kapralov, Michael;Wajc, David
通讯作者：
Wajc, David

A Time-Optimal Randomized Parallel Algorithm for MIS