CAREER: Communication, Information, and Interactive Compression

职业：通信、信息和交互式压缩

• 批准号: 1750443
• 负责人: Gillat Kol
• 金额: $ 50万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-02-01 至 2025-01-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1750443&HistoricalAwards=false
• 关键词: CAREER; Communication; Information; Interactive; Compression

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.

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

项目成果

Interactive Distributed Proofs

交互式分布式证明

• 发表时间: 2018
• 期刊: ACM Symposium on Principles of Distributed Computing
• 作者: Kol, Gillat;Oshman, Rotem;Saxena, Raghuvansh.
• 通讯作者: Saxena, Raghuvansh.

Interactive Compression to External Information

对外部信息的交互式压缩

• 发表时间: 2018
• 期刊: ACM Symposium on Theory of Computing
• 作者: Braverman, Mark;Kol, Gillat.
• 通讯作者: Kol, Gillat.

Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds

通过无噪音蜂鸣下限确定嘈杂的无线电网络下限

• 发表时间: 2023
• 期刊: Innovations in Theoretical Computer Science (ITCS
• 作者: Efremenko, Klim;Kol, Gillat;Paramonov, Dmitry;Saxena, Raghuvansh R.
• 通讯作者: Saxena, Raghuvansh R.

Rounds vs Communication Tradeoffs for Maximal Independent Sets

最大独立集的回合与通信权衡

• 发表时间: 2022
• 期刊: Proceedings annual Symposium on Foundations of Computer Science
• 作者: Assadi, Sepehr;Kol, Gillat;Zhang, Zhijun
• 通讯作者: Zhang, Zhijun

Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut

迈向最大切割优化逼近的多通道流下界

• 发表时间: 2023
• 期刊: Proceedings of the annual ACMSIAM Symposium on Discrete Algorithms
• 作者: Chen, Lijie;Kol, Gillat;Paramonov, Dmitry;Saxena, Raghuvansh;Song, Zhao;Yu, Huacheng
• 通讯作者: Yu, Huacheng