[Theory] UC Theory Seminar

[Alexander Razborov via Theory]

Noah Fleming
Memorial University, Newfoundland
 
 
  
Tuesday, January 21, 2025, at 3:30pm
Kent Chemical Laboratory, Room 120
 
 
 
Title: Proofs, Circuits, and Total Functions
 
Abstract: Recently deep connections between the studies of total search problems (TFNP) and the complexity of theorem proving (proof complexity) have led to a led to the resolution of a large number of important open problems in both areas. This includes a complete understanding of the relationships between the major TFNP subclasses (in the black-box setting), as well as a deeper understanding of interpolation theorems and lifting theorems in proof complexity -- tools which have been highly influential for proving lower bounds in proof and circuit complexity. In this survey talk I will detail why and when these connections between proof complexity and TFNP emerge, as well as some exciting directions for future research. 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250114/5e929637/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.png
Type: image/png
Size: 656565 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250114/5e929637/attachment-0001.png>