BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/825
DTSTAMP:20230914T125939Z
SUMMARY:A Biased Introduction to Proof Complexity
DESCRIPTION:Speaker: Marc Vinyals\n\nAbstract: \nPropositional proof comple
xity is the study of the resources that are needed to prove formulas in pr
opositional logic. Originally developed as an approach to the P vs NP prob
lem\, nowadays proof complexity has got a life of its own\, with one salie
nt application being unconditional lower bounds for search algorithms. In
this talk we will discuss some proof systems with such applications\, name
ly resolution\, polynomial calculus\, and cutting planes\; and review what
are they\, which complexity measures we can associate\, interesting upper
and lower bounds\, and if time permits some open problems.\n
URL:https://www.tcs.tifr.res.in/web/events/825
DTSTART;TZID=Asia/Kolkata:20171117T171500
DTEND;TZID=Asia/Kolkata:20171117T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR