Validating SAT Refutations

Add to your list(s) Download to your calendar using vCal

• Nathan Wetzler, UT Austin
• Tuesday 30 July 2013, 10:00-11:00
• Microsoft Research Ltd, 21 Station Road, Cambridge, CB1 2FB.

If you have a question about this talk, please contact Microsoft Research Cambridge Talks Admins.

This event may be recorded and made available internally or externally via http://research.microsoft.com. Microsoft will own the copyright of any recordings made. If you do not wish to have your image/voice recorded please consider this before attending

We give an overview of our recent work on validating satisfiability refutations. Satisfiability (SAT) solvers are used not only to find a solution for a Boolean formula, but also to make the claim that no solution exists. If no solution is reported, a solver can emit a proof of unsatisfiability, or refutation, which can then be validated by an unsatisfiability proof checker. Ideally, SAT refutations should be: easy to emit, compact, checked efficiently, checked in a trusted way, and expressive. Existing proof formats support at most two of these five properties. We present a new clausal proof format, called DRUP , that uses clause deletion information and can be checked efficiently.

This talk is part of the Microsoft Research Cambridge, public talks series.

This talk is included in these lists:

• Microsoft Research Ltd, 21 Station Road, Cambridge, CB1 2FB
• All Talks (aka the CURE list)
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Guy Emerson's list
• Interested Talks
• Microsoft Research Cambridge, public talks
• Optics for the Cloud
• PMRFPS's
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• personal list
• rp587

Note that ex-directory lists are not shown.