Constructive Complexity Theory 2025

STOC TheoryFest Workshop
Prague, Czech Republic, June 23-25, 2025

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:

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:

Logistics

Registration at STOC 2025 is required for attendance

Organizers