CAREER: Structural Communication Complexity

University Of Memphis, Memphis TN

Investigators

Abstract

The field of communication complexity is about situations where two parties, call them Alice and Bob, each hold a separate piece of data, and they wish to collaboratively solve some computational problem that depends on both their inputs. How much will they need to communicate back-and-forth to achieve their goal? The field encompasses both upper bounds---i.e., the design of protocols that allow Alice and Bob to succeed using only a small amount of communication---as well as lower bounds---which show that no such efficient protocol exists for certain problems (i.e., Alice and Bob will need to communicate many bits to succeed). This serves as a natural model of distributed computing, motivated by big data and cloud computing concerns. More generally, it can be used to model any situation where flow of information between different components of a system forms a bottleneck; for this reason, communication complexity has applications to many other areas of computer science. This project will develop deep technical tools to make progress on several longstanding problems and central issues in communication complexity and its various application areas. The unifying theme of this project is the importation of insights and techniques from structural complexity, which is the area of theoretical computer science devoted to classifying problems according to their inherent computational difficulty. The education component will address the challenges of facilitating flow of ideas between theory and applications, and transitioning students from coding to problem solving to research. One specific type of tool relevant to this project is "lifting theorems", which relate communication complexity to the simpler model of query complexity. The investigator will continue to develop and apply such lifting theorems to address structural questions in communication complexity and beyond. This project will: develop fundamentally new lower bound techniques for powerful communication models, strengthen and unify classic and widely-used results, clarify the delicate relationship between communication and the amount of information Alice and Bob reveal about their inputs, advance the understanding of computational problems concerning communication complexity itself, and use structural insights to deepen the connections with circuit complexity, proof complexity, and data structures. 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.