Description
Combinatorics and Theoretical Computer Science seminar.
Speaker: Rahul Santhanam.
Affiliation: University of Oxford.
Date and Time: Tuesday 09 April, 11:30 am - 12:30pm.
Venue: Ramanujan Hall, Department of Mathematics.
Title: Independence Results in Propositional Proof Complexity.
Abstract: Given the lack of progress on complexity lower bounds, it is
natural to ask whether they are hard to prove, in some formal sense. I
will begin by briefly describing the classical incompleteness results of
Godel and Chaitin, and posing the question for whether there are analogues
of these results in complexity theory.
I will then introduce the finitistic framework of propositional proof
complexity, where we are interested in the existence of polynomial size
proofs verifiable in polynomial time. I will explain what it means to
prove circuit complexity or proof complexity lower bounds in this
framework. Finally, I will describe a strong complexity conjecture for
which it can be shown unconditionally that there are no feasible
propositional proofs, in a certain technical sense.