AF: Small: Intermediate models between communication complexity and query complexity

University Of California-San Diego, La Jolla CA

Investigators

Abstract

Communication complexity has been a vibrant sub-field of computer science for more than 40 years. At its core, it studies distributed problems, where each player receives a part of a problem, and the players need to cooperate and share information in order to find a solution. Many of the celebrated results in the field involve figuring out exactly how much communication is needed to solve certain concrete important problems with relevance in many other domains in computer science. On the other hand, there are only few techniques to understand general communication problems. This is in contrast with the situation in simpler computational models, notably query complexity. It is safe to say that today there is a complete qualitative, and to a large extent quantitative, understanding of the query complexity of generic problems. The focus of this project is on intermediate models, which interpolate between communication complexity and query complexity. The goal is to to understand fundamental open problems in communication complexity in these restricted models, in order to develop new tools and techniques that then may be extended to general communication complexity. The main questions in communication complexity that this award aims to tackle are: * Which functions admit efficient communication protocols? * Are there algebraic, analytic or combinatorial properties that characterize such functions? * What is the structure of efficient communication protocols? * What is the power of randomness in communication complexity? The plan is to consider these questions restricted to a special class of problems, called lifted functions. These contain many natural examples of well-studied functions, and also give rise to natural intermediate models, such as parity decision trees and AND decision trees. These models are more powerful than standard query complexity, and more structured than general communication complexity, and as such are an ideal test bed to develop new techniques. 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.