[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