[Colloquium] Theodoros Papamakarios’ Candidacy Exam-Oct/9/2023

[Devin Davis]

This is an announcement of Theodoros Papamakarios’ Candidacy Exam.

===============================================

Candidate: Theodoros Papamakarios



Date: Monday, October 9th,2023



Time: 4:00pm CST



Location: JCL 390



Title: On Automatability



Abstract: The problem of proof search is central to automated theorem proving, and has been the driving force behind many theoretical advances: Provided that short proofs of a statement exist, how hard is to find one? More concretely, a proof system P is called automatable if there is an algorithm that, given a formula F, finds a P-proof of F in time polynomial in the size of the shortest P-proof of F. In this presentation, I will start by surveying the role of the notion of automatability in proof complexity, in particular how it connects to other important threads (e.g. feasible interpolation, canonical pairs). I will then focus on recent non-automatability results for weak propositional proof systems.



Advisors: Alexander Razborov



Committee Members: Aaron Potechin, Alexander Razborov, and Madhur Tulsiani


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20230925/56da47ac/attachment.html>