CRII: AF: Developing and Applying Connections Between Communication Complexity and Query Complexity

University Of Memphis, Memphis TN

Investigators

Abstract

The aim of computational complexity is to prove theorems that explain the fundamental limits of computation under resource constraints. Two such resources, communication (between different parties) and queries (to the input), have become increasingly important with the trends toward cloud computing and big data. Recent research by the PI and others has uncovered deep connections between these two subfields of complexity theory, namely communication complexity and query complexity, and has applied these connections to resolve several fundamental and long-standing open problems in theoretical computer science and beyond. This project will further develop these connections and explore new applications, which will help identify which problems can and cannot be solved by efficient computational processes in other areas of computer science. The broader impacts of this project include training and supporting the research careers of graduate students, broad dissemination of research findings through online reference resources and expository articles, curriculum development at the institutional level for the integration of research and teaching, involvement of minorities in research, collaboration with mathematicians, and outreach efforts. The connections between communication complexity and query complexity are formalized as "simulation theorems" showing that in certain situations, decision trees can simulate communication protocols for related problems. The PI will develop the mathematical techniques needed to prove new simulation theorems and obtain quantitative improvements to existing ones. These results will contribute to a "unified theory" of communication lower bounds, showing a separation of concerns in which simple problem-specific query complexity lower bounds can be combined with generic (but deep) machinery for handling communication protocols. The project will also explore new applications of such connections, such as obtaining new lower bounds and separations for communication complexity measures, developing a theory of "fine-grained extension complexity" for linear programming, answering structural questions about communication and about how efficiently the complexity of a given function can be estimated, as well as studying fundamental open questions about the behavior of query complexity measures.