Many aspects of computation can be viewed as communication processes. Communication complexity is the mathematical theory aimed at estimating the amount of communication necessary for such processes. Communication complexity arguments can be used to provide estimates on various other resources needed for computation, including time and space (memory) and circuit size. Communication complexity has many applications in different areas including computer networks, VLSI circuits, data structures, cryptography, learning theory and distributed computing.
This project focuses on exploring the connections between communication complexity and the complexity of computational problems in other models of computation. The main objectives of this research are developing new techniques for proving lower bounds on communication complexity, and using these methods to obtain lower bounds on resources in other models. The project addresses problems of randomized and multiparty communication complexity, private information retrieval, and estimating the space requirements of data stream algorithms.
Proving lower bounds on the complexity of specific functions with respect to various resources has been one of the most challenging areas in complexity theory. Communication complexity arguments and techniques originating from communication complexity have been at the core of several lower bound results that are at the boundary of what is achievable by current techniques. The project can potentially lead to new methods for attacking fundamental problems in complexity theory.
