AF: CIF: Small: Communication complexity techniques beyond classical information theory

AF：CIF：小：超越经典信息论的通信复杂性技术

• 批准号: 2006589
• 负责人: Amit Chakrabarti
• 金额: $ 49.76万
• 依托单位: Dartmouth College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-10-01 至 2024-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2006589&HistoricalAwards=false
• 关键词: AF; CIF; Small; Communication; complexity

Communication is central to modern computing systems, which involve data distributed across multiple entities. Developing communication-efficient algorithmic strategies (protocols) to solve problems featuring distributed data is therefore an important practical goal. Correspondingly, communication complexity---which studies the possibilities and limitations of such protocols---is important to foundational research in computer science. In fact, the influence of communication complexity runs much deeper, because the operation of an algorithm can itself be seen as a careful orchestration of information flow from input bits to output bits, which gives rise to a communication protocol between abstract entities. Key questions in communication complexity are: how much efficiency is gained by allowing the communicating parties to (a) use randomized strategies that may err with some small probability, or (b) use a complex pattern of interactive communication as opposed to a simple one? This project will address some such questions, seeking theorems that provably require fresh mathematical ideas, forcing an expansion of our mathematical arsenal. The project aims to grow the foundations of communication complexity either through novel lower bounds or by obtaining surprising new protocols that may teach us algorithmic lessons.Viewing communication as information flow and quantifying this using the machinery of Shannon entropy and Kullback-Leibler divergence is a powerful technique for proving lower bounds on the communication required to accomplish a task. This project's central goal is to make progress on problems where this general paradigm provably cannot work. The investigator has identified some concrete communication tasks where a deterministic solution plausibly requires considerably more resources than a randomized solution, and proposes to prove such separations by developing a more delicate quantification of information flow that is attuned to deterministic communication protocols. Additionally, the project will study a class of communication problems involving parties with asymmetric knowledge (the so-called Arthur-Merlin setting, where one super-player knows all of the distributed input but is not blindly trusted by the other, regular, players), where classical information theory fails to capture the communication from the super-player.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

通信是现代计算系统的核心，它涉及分布在多个实体上的数据。因此，开发通信高效的算法策略（协议）来解决分布式数据的问题是一个重要的实际目标。相应地，通信复杂性--研究这种协议的可能性和局限性--对计算机科学的基础研究很重要。 事实上，通信复杂性的影响要深得多，因为算法的操作本身可以被看作是从输入位到输出位的信息流的精心编排，这产生了抽象实体之间的通信协议。通信复杂性的关键问题是：通过允许通信方（a）使用可能以小概率出错的随机策略，或（B）使用与简单模式相反的复杂交互式通信模式，可以获得多大的效率？ 这个项目将解决一些这样的问题，寻求定理，证明需要新的数学思想，迫使我们的数学武器库的扩展。该项目旨在通过新的下限或通过获得令人惊讶的新协议来增加通信复杂性的基础，这些协议可能会教我们算法课程。将通信视为信息流并使用香农熵和Kullback-Leibler散度的机制对其进行量化是一种强大的技术，用于证明完成任务所需的通信下限。这个项目的中心目标是在这个一般范式被证明不起作用的问题上取得进展。研究人员已经确定了一些具体的通信任务，其中确定性的解决方案合理地需要比随机化解决方案更多的资源，并建议通过开发一个更精细的信息流量化来证明这种分离，该量化与确定性通信协议相协调。此外，本计画将研究一类涉及知识不对称之当事人的沟通问题（所谓的亚瑟-梅林设置，其中一个超级玩家知道所有的分布式输入，但不被其他普通玩家盲目信任），经典的信息论无法捕捉到来自超-该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Adversarially Robust Coloring for Graph Streams

• DOI: 10.4230/lipics.itcs.2022.37
• 发表时间: 2021-09
• 期刊: ArXiv
• 作者: Amit Chakrabarti;Prantar Ghosh;Manuel Stoeckl

Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms

• DOI: 10.1145/3584372.3588681
• 发表时间: 2022-12
• 期刊: Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
• 作者: Sepehr Assadi;Amit Chakrabarti;Prantar Ghosh;Manuel Stoeckl

Streaming algorithms for the missing item finding problem

针对丢失物品查找问题的流式算法

• 发表时间: 2023
• 期刊: SODA 2023
• 作者: Stoeckl, Manuel