[Colloquium] CS Theory Seminar - Tuesday, January 21, 2025

[Jose J Fragoso via Colloquium]

UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS




Noah Fleming
Memorial University, Newfoundland

 [cid:image001.png at 01DB65CF.1E0CE9C0]

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.

Bio: Noah Fleming is an assistant professor in the department of Computer Science at Memorial University. His research interests are in theoretical computer science, in particular on topics in proof complexity, circuit complexity, and total search problems, as well as sublinear algorithms. He received his PhD from the University of Toronto and following that he spent a year as a postdoctoral researcher at UC San Diego, and the Simons Institute, UC Berkeley.







Host: Aaron Potechin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20250121/e1f39e70/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.png
Type: image/png
Size: 1428278 bytes
Desc: image001.png
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20250121/e1f39e70/attachment-0001.png>