Note --- Different Room On Wednesday: the workshop happens in Congress Hall Sun I + II on Wednesday morning, June 25! This differs from the printed schedule.
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 Talks and Online Posters to highlight recent progress, disseminate open problems, and develop collaborations.
- 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
| Monday June 23 | |
| 8:45AM |
Introduction: Formulating Complexity Theory as a Collection of Computational Problems
Marco Carmosino |
|---|---|
| 9:45AM |
Introduction: Bounded Arithmetic (with Examples in Formalizing Classical Algorithms)
Jiatu Li |
| Tuesday June 24 | |
| 8:45AM |
Introduction: Witnessing Theorems — Converting Proofs into Algorithms
Sam Buss |
| 9:45AM | Introduction: Approximate Counting in Bounded Arithmetic
Emil Jeřábek |
| Wednesday June 25 | |
| 8:45AM |
Research: The Proof Analysis Problem
Noel Arteche |
| 9:00AM |
Research: Prime Factorization in Models of PV_1
Ondřej Ježil |
| 9:15AM |
Research: Algorithmic Formulations
Ryan Williams |
| 9:45AM | Panel: Future of Constructive Complexity and Logical Foundations |
Panel Discussion
We will discuss the evolving role of "constructivity" in complexity theory. Participants are:
- Sam Buss
- Ján Pich
- Pavel Pudlák
- Iddo Tzameret
- moderator: Marco Carmosino
Logistics
Registration at STOC 2025 is required for attendance
Organizers
- Marco L. Carmosino, IBM
- Stefan Grosser, McGill University
- Neil Thapen, Czech Academy of Sciences
- Iddo Tzameret, Imperial College London