MIAO/BARC talk by Noah Fleming

Tuesday, November 3, 2026, 14:00-15:00, Noah Fleming, Assistant Professor at Lund University in Sweden, member of the MIAO group and BARC community, will be giving a talk on "Separations in the Random Oracle Model from Proof Complexity".

Abstract:
TFNP is the total search problem analogue of NP. It contains a ton of important computational problems which do not appear to admit search-to-decision reductions. These problems come from a wide range areas such as game theory and cryptography. The random oracle model augments the standard TFNP definitions to allow access to randomness. In this model, the TFNP class PWPP captures collision-resistant hash functions, while UEOPL captures indistinguishibility obfuscation.

Recently, it has been revealed that proof complexity—the study of what is efficiently provable—is intimately connected to TFNP. In this talk we will show how these connections to proof complexity can be extended to the black-box random oracle model. Then, we will use these to obtain a number of surprising black-box (oracle) separations and inclusions, UEOPL = FP and every other major class does not reduce to FP in the random oracle model. This is joint work with Toniann Pitassi, Dima Sokolov, Oliver Korten, Artur Riazanov, Tianqi Yang, Daniel Mitropolsky, and Ziyi Guan).

Bio:
Noah Fleming is an Assistant Professor at Lund University. He studies proof complexity and its applications to total NP search problems, circuit complexity, and communication complexity. Prior to this, he was an Assistant Professor at Memorial University, and completed his PhD at the University of Toronto.