Tata Institute of Fundamental Research
Independence Results in Propositional Proof Complexity
STCS Seminar
Speaker:
Rahul Santhanam (University of Oxford)
Organiser:
Arkadev Chattopadhyay
Date:
Thursday, 11 Apr 2019, 16:30 to 17:30
Venue:
A-201 Seminar Room
(Scan to add to calendar)
Abstract:
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.
(Based on joint work with Jan Pich).
| Speaker: | Rahul Santhanam (University of Oxford) |
| Organiser: | Arkadev Chattopadhyay |
| Date: | Thursday, 11 Apr 2019, 16:30 to 17:30 |
| Venue: | A-201 Seminar Room |
(Scan to add to calendar)
Abstract:
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.
(Based on joint work with Jan Pich).
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.
(Based on joint work with Jan Pich).