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)

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).