BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1066
DTSTAMP:20230914T125949Z
SUMMARY:Proof Complexity of MaxSAT Resolution
DESCRIPTION:Speaker: Gaurav Sood (Institute of Mathematical Sciences\nChenn
ai\, Tamil Nadu)\n\nAbstract: \nZoom details:\nMeeting ID: 613 566 8340\nP
assword: 183102\nAbstract: Boolean satisfiability (SAT) is the quintessent
ial NP-complete problem. It has given rise to many areas of research wit
hin theoretical computer science\, one of them being proof complexity. Gi
ven a proof system for SAT\, we ask questions of the following form: is th
ere a short proof that an unsatisfiable formula is unsatisfiable?\n\nMaxSA
T is the related problem of determining the maximum number of satisfiable
clauses\, and like SAT\, it has its own proof systems. In this talk\, we
will study a proof system for MaxSAT proposed by Bonet et al. in 2007\, an
d compare it with proof systems for SAT. This is joint work with Yuval Fil
mus\, Meena Mahajan and Marc Vinyals.\n
URL:https://www.tcs.tifr.res.in/web/events/1066
DTSTART;TZID=Asia/Kolkata:20200625T143000
DTEND;TZID=Asia/Kolkata:20200625T153000
END:VEVENT
END:VCALENDAR