University of Cambridge > > Microsoft Research Cambridge, public talks > Validating SAT Refutations

Validating SAT Refutations

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

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 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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2023, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity