Abstractions in Satisfiability Solvers

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

• Vijay D'Silva, Oxford University
• Friday 09 September 2011, 11:00-12:00
• Small lecture theatre, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge.

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

Modern satisfiability solvers combine an elegant algorithm with clever heuristics and efficient engineering to achieve extremely high performance. I will show that the Conflict Driven Clause Learning algorithm in modern solvers has a natural characterisation in the framework of abstract interpretation. In particular, SAT solvers operate on a strict abstraction of propositional logic. This is surprising because an imprecise abstraction is used to obtain precise results. Time permitting, I will discuss how one may derive verification algorithms from satisfiability algorithms.

I assume no background in either SAT solving or abstract interpretation.

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

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge Big Data
• Cambridge University Engineering Department Talks
• Centre for Smart Infrastructure & Construction
• Chris Davis' list
• Featured lists
• Guy Emerson's list
• Methodology in design research
• Microsoft Research Cambridge, public talks
• PMRFPS's
• School of Technology
• Small lecture theatre, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• rp587

Note that ex-directory lists are not shown.