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

通信是现代计算系统的核心，现代计算系统涉及跨多个实体分布的数据。因此，开发通信高效的算法策略(协议)来解决具有分布式数据特征的问题是一个重要的实用目标。相应地，通信复杂性-研究这种协议的可能性和局限性-对计算机科学的基础研究是重要的。事实上，通信复杂性的影响要深得多，因为算法的操作本身可以被视为从输入比特到输出比特的信息流的精心编排，这导致了抽象实体之间的通信协议。通信复杂性中的关键问题是：允许通信方(A)使用可能以小概率出错的随机化策略，或(B)使用交互通信的复杂模式而不是简单模式，可以获得多大的效率？这个项目将解决一些这样的问题，寻找可以证明需要新的数学思想的定理，迫使我们扩大数学武器库。该项目旨在通过新的下界或通过获得令人惊讶的新协议来增加通信复杂性的基础，这些协议可能会给我们带来算法上的教训。将通信视为信息流，并使用Shannon熵和Kullback-Leibler发散机制来量化信息流，是证明完成任务所需通信的下界的强大技术。这个项目的中心目标是在这一通用范式显然不起作用的问题上取得进展。研究人员已经确定了一些具体的通信任务，其中确定性解决方案似乎比随机解决方案需要相当多的资源，并建议通过开发符合确定性通信协议的更精细的信息流量化来证明这种分离。此外，该项目将研究一类涉及具有不对称知识的各方的沟通问题(所谓的Arthur-Merlin设置，其中一个超级玩家知道所有分布式输入，但不被另一个常规玩家盲目信任)，其中经典信息理论无法捕获来自超级玩家的沟通。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.