February 2019
DIMACS announces the start of its Special Focus on Lower Bounds in Computational Complexity, which will run through the fall of 2021. The special focus is organized by Eric Allender (Rutgers), Mark Braverman (Princeton), Gillat Kol (Princeton), Swastik Kopparty (Rutgers), Periklis Papakonstantinou (Rutgers), Toniann Pitassi (University of Toronto and visitor at the Institute for Advanced Study), and Ran Raz (Princeton).
The DIMACS special focus is part of the DIMACS/Simons Collaboration on Lower Bounds in Computational Complexity, a Research Coordination Network (RCN) led by DIMACS and the Simons Institute for the Theory of Computing to advance research on lower bounds in complexity theory. Activities of the broader DIMACS/Simons Collaboration began in the fall semester of 2018 with the Simons Institute program on Lower Bounds in Computational Complexity and now continue in association with the DIMACS special focus.
To add yourself to the mailing list for the DIMACS Special Focus on Lower Bounds in Computational Complexity, please go here.
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 algorithmic techniques, this involves discovering lower bounds on computational resource requirements. Such lower bounds are computational analogues to physical laws such as the law of conservation of energy. This is a particularly opportune time 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, communication complexity, and on the complexity of data structure access mechanisms.
The study of lower bounds requires tools and methods from many areas of mathematics, including analysis, geometry, algebra, probability theory, information theory, invariant theory and more. Several general principles guide lower bound proofs, but despite much effort, the main questions in most models—including the P vs. NP question and its many offshoots—remain unsolved.
The problems to be addressed by participants of the special focus (and the RCN more broadly) are among the most difficult and consequential problems in computer science. As such, proving lower bounds in computational complexity requires time and opportunities for interaction and collaboration that can be sustained over a period of years. By providing such opportunities, the special focus aims to contribute 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.
The Special Focus on Lower Bounds in Computational Complexity includes research visits, collaboration with New York Area Theory Day, and workshops on related themes. Events that are currently in planning are:
- DIMACS Day of Complexity Tutorials, in conjunction with CCC'19
- Workshop on Information-Theoretic Methods in Complexity Theory
- Workshop on Meta-Complexity, Barriers, and Derandomization
- Working Group on Data Structure Lower Bounds
- Workshop on Arithmetic and Boolean Circuit Complexity
Both DIMACS and the Simons Institute coordinate many of their activities around designated scientific themes. Themed programs at the Simons Institute typically span a single semester, while DIMACS special foci typically span several years. Like preceding DIMACS/Simons Collaborations in Cryptography and on Bridging Continuous and Discrete Optimization, the Collaboration on Lower Bounds leverages these different timescales. The intense focus and energy of the Simons program during the fall of semester of 2018 launched the collaboration and built momentum around the theme, while the longer time afforded by the DIMACS special focus will allow ideas to broaden and develop more fully.
The DIMACS/Simons Collaboration on Lower Bounds in Computational Complexity is funded by the National Science Foundation as a research coordination network under award CCF-1836666. The Simons Institute program was also supported in part by a grant from the Simons Foundation.
Printable version of this story: [PDF]