[Colloquium] Theodoros Papamakarios’ Candidacy Exam-Oct/9/2023
Devin Davis
devind at uchicago.edu
Mon Oct 9 08:59:31 CDT 2023
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/20231009/e4103949/attachment-0001.html>
More information about the Colloquium
mailing list