The DIMACS/Simons Collaboration on Lower Bounds in Computational Complexity is a research coordination network (RCN) led by DIMACS and the Simons Institute for the Theory of Computing to conduct activities devoted to advancing research on lower bounds in complexity theory. The Collaboration features activities at both DIMACS and the Simons Institute, bringing together researchers from different areas of theoretical computer science and related mathematics to address some of the most vexing problems in theoretical computer science.
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. 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 DIMACS/Simons Collaboration on Lower Bounds in Computational Complexity aims to hasten progress on these important problems by enabling sustained collaboration and intense focus over a period of several years.
The Collaboration kicks off with an intensive program on Lower Bounds in Computational Complexity at the Simons Institute during the fall of 2018. Beginning with a Boot Camp to introduce key themes, the Simons program brings together roughly 75 long-term participants (including students) in residence at the Simons Institute. The Simons program also includes three additional workshops on:
The program at the Simons Institute program is immediately followed by the DIMACS Special Focus on Lower Bounds in Computational Complexity, beginning in January 2019 and continuing through 2024. The DIMACS program builds on the intensive activity of the Simons program to engage more people and allow more time for ideas to develop. The special focus aims to advance research related to lower bounds on computational complexity through research visits, sponsorship of NY Area Theory Day, and five additional events:
- Complexity Tutorials in Conjunction with CCC’19;
- Workshop on Information-Theoretic Methods in Complexity Theory;
- Workshop on Meta-Complexity, Barriers, and Derandomization;
- Workshop on Lower Bounds and Frontiers in Data Structures; and
- Workshop on Arithmetic and Boolean Circuit Complexity.
As the special focus progresses, new events and activities that align with the theme may be added. For the most up-to-date list of special focus activities, please see the calendar for the Special Focus on Lower Bounds on Computational Complexity.
The DIMACS/Simons Collaboration on Lower Bounds in Computational Complexity is led by a Steering Committee of:
- Eric Allender, Rutgers University
- Mark Braverman, Princeton University
- Shafi Goldwasser, UC Berkeley
- Gillat Kol, Princeton University
- Swastik Kopparty, Rutgers University
- Periklis Papakonstantinou, Rutgers University
- Toniann Pitassi, University of Toronto
- Ran Raz, Princeton University
- Rebecca Wright, Rutgers University.
The DIMACS/Simons Collaboration on Lower Bounds in Computational Complexity is supported by the National Science Foundation under grant number CCF- 1836666.