CAREER: Communication, Information, and Interactive Compression

信息论对实践界和理论界都产生了深远的影响，几乎在科学的每一个分支中都有应用。在互联网和数据密集型应用兴起的今天，信息理论尤其相关。近年来，这些应用中的许多都是交互的，涉及到多个通信方，并且交互的趋势越来越大。交互信息论是信息论和计算复杂性理论交界处的一个新的研究领域。它区别于经典信息论的关键因素是，它研究的是各方相互作用、信息流动不止一个方向的问题。这个项目的目的是加深我们对交互信息理论的理解。具体地说，它考虑了交互式压缩问题，这是数据压缩问题的交互式类比。在非正式的情况下，著名的数据压缩定理暗示，每条消息都可以被压缩成它的信息内容，使用熵函数来衡量。交互压缩问题是指几方之间的每个通信协议的文本是否可以被压缩成(大致)它的“信息内容”。对这个问题的肯定的回答将产生一种证明几乎紧凑的通信复杂性下界的有效方法，并可能对理论计算机科学中与其密切相关的其他核心问题有所启发，例如不同模型的直和和并行重复问题，以及对数等级猜想。好的压缩协议还在协议设计中提出了一种新的范例，其中一个人对协议所揭示的信息进行优化，然后应用压缩方案来获得信息较少的协议。交互压缩的研究也可能会引起隐私和信息理论社区的兴趣，他们已经考虑了类似的概念。PI将指导学生，提供教程，并为计算机科学和电气工程专业的学生创建一门关于交互信息的新课程。

Information theory had a profound impact on both the practical and theoretical communities, finding application in almost every branch of science and beyond. Information theory is especially relevant today with the rise of the internet and data-intensive applications. Lately, many of these applications are interactive, involving several communicating parties, and the trend for more interaction is growing.Interactive information theory is a new field of study at the interface between information theory and computational complexity theory. The key ingredient that sets it apart from classical information theory is that it studies problems where parties are interacting and information flows in more than one direction. The goal of this project is to deepen our understanding of interactive information theory. Specifically, it considers the interactive compression problem, which is the interactive analogue of the data compression problem. Informally, the celebrated data compression theorems imply that every message can be compressed to its information content, measured using the Entropy function. The interactive compression problem asks whether the transcript of every communication protocol between several parties can be compressed to (roughly) its "information content."An affirmative answer to this problem would yield a powerful method for proving nearly tight communication complexity lower bounds, and may shed light on other central problems in theoretical computer science that are closely related to it, such as the direct sum and parallel repetition problems for different models, and on the log-rank conjecture. Good compression protocols also suggest a new paradigm in protocol design, where one optimizes over the information revealed by the protocol and then applies a compression scheme to obtain a protocol with low information. The study of interactive compression can also be of interest to the privacy and information theory communities, which have considered similar notions.The PI will mentor students, give tutorials and create a new course on interactive information for Computer Science and Electrical Engineering majors.