Date: September 14, 2026
Title: TFNP Separations From Proof Complexity
Speaker: Noah Fleming, Assistant Professor, Lund University, Department of Computer Science, Visiting Professor, Columbia University
Abstract: TFNP is the total search problem analogue of NP. It contains a ton of important problems which do not appear to admit search-to-decision reductions, in areas such as game theory, cryptography, and complexity theory. Recently, it has been revealed that proof complexity—the study of what is efficiently provable—is intimately connected to TFNP. This has led to a separation between every major TFNP class in the black-box/oracle setting, as well as a new structural interpretation of proof complexity. In this talk we will survey the connections between TFNP and proof complexity, as well as discuss a new result (joint work with Toniann Pitassi, Dima Sokolov, Oliver Korten, Artur Riazanov, and Tianqi Yang) which shows that proof complexity can also be used to obtain separations between TFNP classes in the random oracle model!
