The DIMACS Special Focus on Lower Bounds in Computational Complexity 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.
Computational lower bounds are fundamental laws that recognize that at least a certain amount of resources (running time/memory/communication) are needed to solve the given problem. Such lower bounds are computational analogues to physical laws such as the law of conservation of energy. 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.
Organizing Committee:
- Eric Allender, Rutgers University
- Mark Braverman, Princeton University
- Gillat Kol, Princeton University
- Swastik Kopparty, Rutgers University
- Periklis Papakonstantinou, Rutgers University
- Toniann Pitassi, University of Toronto and visitor at the Institute for Advanced Study
- Ran Raz, Princeton University
DIMACS Focal Point Person: Tamra Carpenter, DIMACS
Send an email to the organizers: dimacs_lowerbounds_committee (at) email.rutgers.edu.
Opportunities to Participate:
- Calendar of Events: A variety of workshops and other events are part of the Special Focus.
- Research Visits: There are funds for research visits associated with the Special Focus or in support of collaborations stemming from the activities associated with the DIMACS/Simons Collaboration on Lower Bounds in Computational Complexity. Visits can be hosted at Rutgers, at a DIMACS partner location, at the Simons Institute, or anywhere else appropriate that supports new collaborations coming out of the Collaboration on Lower Bounds in Computational Complexity.
- Graduate Student Support: The Special Focus has funds set aside for graduate students interested in attending workshops. Students interested in attending Special Focus workshops are encouraged to apply to the workshop organizers or to the Special Focus organizers.
- Undergraduate Summer Research: The Special Focus will provide support for one undergraduate student each summer to participate in the DIMACS REU program and conduct research in complexity theory, mentored by a Rutgers faculty member or visitor associated with the program. Interested students should apply to the DIMACS REU program, noting their interest in complexity theory in their personal statement.
- New York Area Theory Day: Theory Day is a long-running lecture series on recent results in theoretical computer science. Theory Day is held twice yearly, alternating its location between Columbia and NYU. Each Theory Day features several presentations about state-of-the-art advances in various areas of theoretical computer science. The Special Focus is collaborating with the New York Area Theory Day to make funds available to support travel by speakers—particularly students and postdocs working in complexity—from outside the local geographic area.
- Materials and Publications: We anticipate that activities of the Special Focus will be documented through slides and video of workshop presentations as well as research publications.
Join the Mailing List:
If you would like to receive updates and announcements about future activities, you can subscribe to the mailing list for the Special Focus on Lower Bounds in Computational Complexity. Alternatively, you can contact the DIMACS Publicity Coordinator and ask to be placed on the SF_LowerBounds mailing list.
Sponsorship:
The DIMACS Special Focus on Lower Bounds in Computational Complexity is supported by DIMACS and its partners, and by the National Science Foundation under grant number CCF-1836666.