About
The theoretical study of computational intractability is one of the most interesting and challenging endeavors in our quest to understand the capabilities of computational devices. This study takes many forms, depending on the exact model being investigated and the assumptions being made. It requires tools and methods from many areas of mathematics, including analysis, geometry, algebra, probability theory, information theory, invariant theory and more. By now, there are several general principles that guide lower bound proofs, but despite much effort the main questions in most models remain unsolved.
The problem of proving "impossibility" results in mathematics has been studied for ages. The focus of this program is on proving impossibility results in concrete computational models. Of course, the most fundamental challenge in this direction is the P versus NP question and its many offshoots, but this challenge seems out of reach at the present time. Nevertheless, many other basic and interesting questions are still open in models like boolean circuits, branching programs and formulas, algebraic computation, communication complexity, streaming algorithms, data structures, extension complexity of polytopes, and so forth.
The program will explore three distinct classes of models: interactive models, boolean devices and algebraic methods. Within these models, the program will aim to develop viable research programs for making progress on major open problems in computational lower bounds, identify and investigate connections between different approaches for proving lower bounds in an attempt to unify them, and revisit old approaches and try to revive them using present technology.
Specific challenges that the program will focus on include the following: compression of communication protocols; query complexity in data structures; P versus NC1 and the KRW conjecture; lifting theorems; matrix rigidity; NEXP versus P/poly and uniform lower bounds; limitations of the “constant depth chasm” mechanism; and new approaches towards the VP versus VNP problem.
This program is supported in part by the National Science Foundation, as part of the DIMACS/Simons Institute Collaboration on Lower Bounds in Computational Complexity, and by the Patrick J. McGovern Foundation.
