[Proof Complexity] MIAO seminar Thu Apr 24 at 14:00 CET with Noah Fleming: Proofs and search problems

Jakob Nordström jn at di.ku.dk
Wed Apr 16 16:10:38 CEST 2025


Dear all,

On Thursday next week, we have the pleasure of welcoming Noah Fleming 
from Memorial University, who will present a seminar titled "Proofs and 
search problems". You find the abstract at the bottom of this message.

We will run this as a MIAO hybrid seminar at Lund University. Local 
participants are warmly welcome to seminar room E:1426 at Ole Römers väg 
3, while other participants are equally warmly welcome to join virtually 
at https://lu-se.zoom.us/j/61925271827 . Please feel free to share this 
information with colleagues who you think might be interested. We are 
also hoping to record the seminar and post on the MIAO Research YouTube 
channel https://youtube.com/@MIAOresearch for people who would like to 
hear the talk but cannot attend.

More information about the MIAO seminar series can be found at 
https://jakobnordstrom.se/miao-seminars/ . If you do not wish to receive 
these announcements, or receive several copies of them, please send a 
message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

/Thursday Apr 24 at 14:00 in seminar room E:1426, Ole Römers väg 3, Lund 
University, and on Zoom
*Proofs and search problems
*(Noah Fleming, Memorial University)
/
Recently deep connections between the study of theorem proving (proof 
complexity) and the computability of total search problems (TFNP) have 
led to the resolution of a number of important open problems in both 
areas. This has positioned proof complexity as a valuable tool for the 
study of total search problems, providing a complete understanding of 
the relationships between the major TFNP subclasses (in the black-box 
setting). As well, it has led to a theory underlying the highly 
impactful connections between provability and computability via 
interpolation and lifting theorems. In this survey talk I will detail 
how these connections emerge, their applications and limitations, as 
well as some exciting recent work which extends these connections beyond 
(black-box) TFNP.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +45 28 78 38 11 / +46 70 742 21 98
https://jakobnordstrom.se


More information about the Proof-Complexity mailing list