IMSc Webinar

(Webinar) Proof complexity of MaxSAT Resolution

Gaurav Sood

IMSc

(Webinar: to join, follow the link meet.google.com/vca-xmye-osb ) Proof complexity studies questions of the following form: Given a proof system for SAT, is there a short proof that an unsatisfiable formula is unsatisfiable? MaxSAT 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, and compare it with proof systems for SAT. This is joint work with Yuval Filmus, Meena Mahajan and Marc Vinyals.