BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/956
DTSTAMP:20230914T125944Z
SUMMARY:Independence Results in Propositional Proof Complexity
DESCRIPTION:Speaker: Rahul Santhanam (University of Oxford)\n\nAbstract: \n
Abstract: Given the lack of progress on complexity lower bounds\, it is na
tural 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.\nI will then introduce the finitistic
framework of propositional proof complexity\, where we are interested in t
he existence of polynomial size proofs verifiable in polynomial time. I wi
ll explain what it means to prove circuit complexity or proof complexity l
ower bounds in this framework. Finally\, I will describe a strong complexi
ty conjecture for which it can be shown unconditionally that there are no
feasible propositional proofs\, in a certain technical sense.\n(Based on j
oint work with Jan Pich).\n
URL:https://www.tcs.tifr.res.in/web/events/956
DTSTART;TZID=Asia/Kolkata:20190411T163000
DTEND;TZID=Asia/Kolkata:20190411T173000
LOCATION:A-201 Seminar Room
END:VEVENT
END:VCALENDAR