CAREER:Coding and Information Theory for Interactive Computing

这个项目将经典的信息和编码理论扩展到交互式交流环境中。信息和编码理论让我们对互联网或移动网络等网络传输信息的能力有了近乎完美的理解。然而，这种理解通常限于非交互设置：存在发送者和接收者，目标是尽可能快速且可靠地将消息从发送者传输到接收者。近年来，云计算等应用引发了交互通信问题，其目标是在通信通道上实现完整的功能，而不仅仅是传输数据。研究人员研究围绕着将信息论方法扩展到交互问题的基本问题。该项目旨在确定交互计算的极限，并开发新的编码算法，使交互计算更加高效。研究人员正在开发的关键技术概念是信息复杂性。信息复杂性是Shannon熵对交互问题的自然推广。香农的信息量衡量的是随机消息中包含的信息量。交互信息复杂性衡量的是参与方感知到的交互计算中包含的信息量。该项目开发这一概念是为了解决通信复杂性中的问题，如直和定理、多方通信复杂性和难度放大。更广泛地说，研究人员开发了将信息论应用于计算复杂性的技术，目的是扩大可用的技术工具箱，以解决复杂性理论中的基本问题。

This project expands classical information and coding theories to the interactive communication settings. Information and coding theories give us a near-perfect understanding of the capacity of networks, such as the Internet or mobile networks, to transmit information. This understanding however, is generally limited to the non-interactive setting: there is a sender and a receiver and the goal is to transmit a message from the sender to the receiver as quickly and reliably as possible. In recent years, applications such as cloud computing gave rise to interactive communication problems, where the goal is to implement a whole functionality over a communication channel, rather than just transmit data. The investigators study fundamental questions surrounding extending information theory approaches to interactive problems. The project aims to establish the limits of interactive computation, as well as to develop new encoding algorithms that make interactive computing more efficient.The key technical concept being developed by the investigators is that of information complexity. Information complexity is the natural generalization of Shannon's entropy to interactive problems. Shannon's entropy measures the amount of information contained in a random message. Interactive information complexity measures the amount of information contained in the interactive computation, as perceived by the participating parties. The project develops this concept to address problems in communication complexity, such as direct sum theorems, multi-party communication complexity, and hardness amplification. More broadly, the investigators develop techniques for applying information theory to computational complexity, with the aim of expanding the technical toolbox available to attack fundamental problems in complexity theory.