NSF-BSF: AF: Small: Lower bounds on concrete complexity

Computational complexity theory is the study of computation that can be carried out using limited computational resources like processing power, memory and communication. The goal is to investigate the mathematical possibilities and limits of efficient computation. Modern life continues to be transformed by the use of computational devices that have access to limited resources, like cell phones.

It is invaluable to understand what can be computed by such devices. Results in complexity theory provide a guide to help implement efficient solutions using such devices. In this project, we investigate fundamental questions about communication, viewed as a scarce resource.

For example, if the best solution to problem A requires communication X, and the best solution to problem B requires communication Y, what is the communication required to solve both problems at the same time? It turns out that the answer need not be X+Y. The investigators will build mathematical tools to address this kind of question.

In order to pursue these goals, they will use ideas from various mathematical disciplines like geometry, analysis and combinatorics.

The project will focus on several fundamental questions related to communication complexity. The investigators will study questions related to understanding the limits of compressing interactive communication protocols, proving lower bounds on the running times of certain kinds of algorithms, and proving the log-rank conjecture. This includes an approach to proving tight lower bounds for the famous disjointness problem in communication complexity.

In the realm of boolean circuits, the focus is on proving lower bounds for arithmetic circuits with bounded coefficients and understanding boolean circuits that use threshhold gates. With regards to the extension complexity of polytopes, the project focuses on proving new lower bounds on approximations of polytopes, as well as exploring a new connection between extension complexity and circuit lower bounds.

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.