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

Dartmouth College, Hanover NH

Investigators

Abstract

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.