CAREER:Coding and Information Theory for Interactive Computing

职业：交互式计算的编码和信息论

• 批准号: 1149888
• 负责人: Mark Braverman
• 金额: $ 45万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-01-15 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1149888&HistoricalAwards=false
• 关键词: CAREER; Coding; Information; Theory; Interactive

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.

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