CAREER: A Theory of Error Correction for Interactive Communication

本项目旨在发展互动式沟通中纠错的理论和方法。香农颇具影响力的《通信数学理论》为单向通信建立了这样一个理论。编码理论随后产生了在不可靠信道上可靠数据传输的高效计算方法。虽然纠错码在过去几十年里改变了通信技术，但现代通信环境往往超越了单向传输，而是需要许多交错的交互式通信。为这样的现代系统开发与良好纠错码相当的交互式代码是一项艰巨得多的任务，最近引起了人们的注意，并取得了令人鼓舞的初步成功。该项目将进一步推进在噪声存在下可靠交互通信的可能性、局限性和理论基础的基本问题，从而为可靠交互通信的坚实数学和计算理论做出贡献。该项目还具有很强的教育成分，支持通过教育和推广来激励本科生、研究生、科学界和公众的若干举措。该项目研究了一系列不同的“经典”问题，例如确定交互式通信中纠错的基本通信速率限制，以及树代码的明确构造，树代码是一种强大但难以捉摸的在线代码类型。该项目还考虑了交互编码方案的更广泛背景及其在理论计算机科学的其他领域的广泛适用性，包括密码学，隐私和内存高效错误弹性计算。

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.