CAREER:Coding and Information Theory for Interactive Computing

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

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.