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.