Satisfiability: connecting logic and probability

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

• ramdas aaditya, CMU and intern
• Wednesday 22 August 2012, 14:00-15: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

In this talk, I shall discuss and connect some of the main ideas surrounding the vast and interesting topic of Boolean CNF Satisfiability. The motivation shall be the possible development of new insights or algorithms, or an understanding of why some algorithms for SAT might or might not work better than others. I shall start with the above graph but without any edges, and go on to fill in all the edges of the graph through the talk, in near anticlockwise order from the bottom (if there is shortage of time, I will not talk about the two player pebble games, and if there is even less time then I’ll just gloss over proof complexity).

some keywords:

AI – logic + probability, CNF -SAT, belief propagation, threshold phenomena, factor graphs, survey propagation, integer programming, LP relaxations, convergent message passing, dual decomposition, clause driven conflict learning, resolution, extended resolution, marginal polytope, convex hulls, cutting planes, chvatal-gomory, sherali-adams, lovasz-schrijver, lasserre, proof systems, size/width/rank/space of proofs, etc

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 University Engineering Department Talks
• Centre for Smart Infrastructure & Construction
• Featured lists
• Methodology in design research
• Microsoft Research Cambridge, public talks
• School of Technology
• Small lecture theatre, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge
• de239's list
• engineering

Note that ex-directory lists are not shown.