RCN: DIMACS/Simons Collaboration on Lower Bounds in Complexity Theory

One of the main goals of theoretical computer science is to understand the computational resources needed to solve a given computational problem. Along with the development of new algorithms and new algorithmic techniques, this involves discovering lower bounds on computational resource requirements. The DIMACS/Simons Collaboration on Lower Bounds in Complexity Theory, funded by this award, will speed up progress on some of the most vexing problems in theoretical computer science by enabling sustained collaboration and intense focus over a period of several years and will strengthen the research community whose work is dedicated to proving lower bounds on computational complexity. The research questions addressed by the project are of profound theoretical interest in and of themselves, and are also motivated by extremely pressing practical problems: for example, the cryptographic protocols that currently underlie the internet-based economy all rely on the unproven computational intractability of problems in the complexity class NP.

The project seeks to focus attention on lower bounds because there have been some remarkable recent breakthroughs in proving lower bounds in Boolean circuit complexity, arithmetic circuit complexity, and communication complexity, and on the complexity of data structure access mechanisms. The project begins with an intensive program at the Simons Institute for the Theory of Computing at Berkeley in the fall semester of 2018 and continues with a 2.5-year special focus led by DIMACS at Rutgers that will expand the project to include more people and more topics. By providing opportunities to sustain collaborations and share ideas over a span of years, the RCN contributes to research that strives for a more complete and unified theory of the techniques for proving lower bounds, more powerful abstractions, and ultimately, new breakthroughs in computational lower bounds. This Research Collaboration Network enables expansion of the Fall 2018 Simons program, including additional long-term participants and new activities for graduate students and early-career fellows. The DIMACS special focus includes three workshops (Meta-Complexity, Barriers, and Derandomization; Arithmetic and Boolean Circuit Complexity; and Information-Theoretic Methods in Complexity Theory), a day of tutorials in conjunction with the 2019 Conference on Computational Complexity, a focused working group on Data Structure Lower Bounds, support for the twice-yearly New York Area Theory Day, a robust visitor program, and summer research for undergraduates.

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.