Why do the main questions of complexity theory remain open after decades of intensive effort? This workshop covers exciting new results and tools that are beginning to explain the inherent difficulty of open questions in complexity theory, with two main themes. The algorithmic method formulates complexity separations as computational problems. Feasible meta-mathematics studies (un)provability of complexity-theoretic statements in formal systems weaker than Peano Arithmetic, but still capable of proving many key theorems about algorithms and complexity. We will have:
- Introductory Talks that demonstrate how these seemingly-distinct approaches are inextricably linked, and discuss how connections between them have driven recent progress.
- Research Spotlights to highlight recent progress in both algorithmic formulations and meta-mathematical foundations of complexity theory in context.
- Short Talks and Online Posters to disseminate open problems and develop collaborations — call TBA soon.
- Finally, a Panel Session to conclude the workshop with discussion of past and future work on constructive complexity theory and logical foundations.
The location of STOC TheoryFest 2025 in Prague is a special opportunity for this workshop. Prague is home to a circle of researchers with an enormous impact on the meta-mathematics and logical foundations of complexity theory.
Schedule (preliminary)
| Monday June 23 | |
| 8:45AM |
Introduction: Formulating Complexity Theory as a Collection of Computational Problems
Marco Carmosino |
|---|---|
| 9:45AM |
Introduction: Translating Complexity Statements into Logic & Studying Their Provability
Emil Jeřábek |
| Tuesday June 24 | |
| 8:45AM |
Introduction: Witnessing Theorems — Converting Proofs into Algorithms
TBA |
| 9:45AM | Short Talks
Call Forthcoming, Details TBA |
| Wednesday June 25 | |
| 8:45AM |
Research Spotlight: Algorithmic Formulations
TBA |
| 9:15AM |
Research Spotlight: Logical Foundations
TBA |
| 9:45AM | Panel Discussion: Future Directions in Constructive Complexity and Logical Foundations |
Panel Session
Moderated by Rahul Santhanam. Confirmed participants include:
- Sam Buss
- more panelists TBA...
Call for Short Talks
TBA.
Call for Online Posters
TBA.
Logistics
Registration at STOC 2025 is required for attendance; more details TBA.
Organizers
- Marco L. Carmosino, IBM
- Stefan Grosser, McGill University
- Neil Thapen, Czech Academy of Sciences
- Iddo Tzameret, Imperial College London