AAAI-08 / LION 3 Tutorial
Satisfied by Message Passing:
The goal of this tutorial is to discuss the basics of and the state of the art in applying message passing techniques to solve difficult combinatorial problems. Some of these attempts, specifically the survey propagation algorithm for random k-SAT and k-coloring, have seen astonishingly successful, and have also shed light into the solution space structure of such problems. This is a promising and relatively new area at the intersection of combinatorial and probabilistic reasoning, whose understanding can be extremely beneficial for AI researchers.
|To be presented at||:||AAAI-08 Conference, Tutorial SP3||LION 3 Conference|
|Date and time||:||Sunday, July 13, 2008; 2pm-6pm||Saturday, Jan 17, 2009; 1:30-3pm|
|Location||:||Hyatt Regency McCormick Place, Chicago, IL||Faculty of Science, University of Trento|
Download: tutorial slides (ppt, pdf), 4-per-page handouts pdf
Printed handouts of these slides will also be available at the time of the tutorial for all registered participants.
Pushing the boundary of practical solvability of certain combinatorial problems, such as Boolean satisfiability (SAT) or graph coloring, has far reaching practical consequences. This tutorial will introduce an exciting and relatively new algorithm for such problems called survey propagation. Stemming from physics research, survey propagation is so far the only known approach successful at solving hard random SAT problems with one million variables in a few minutes on a desktop computer, performance which is clearly beyond the reach of mainstream SAT solvers. The key of survey propagation's success lies in its ability to quickly compute an approximate solution of a related problem using a message passing process, and use that to solve the original task.
The tutorial, after covering the necessary background in message passing algorithms, will discuss various research aspects of SP. How can one understand survey propagation using the "usual language" of computer science? How does it relate to the known concept of belief propagation? Is it possible to extend the success of survey propagation to problems beyond random SAT? We will present the state of the art in understanding of survey propagation, as well as provide a step-by-step introduction to the subject.
Prerequisite Knowledge: This tutorial will be accessible to anyone with a basic understanding of Boolean formulas, probabilities, and combinatorial arguments. Familiarity with standard algorithm for SAT and graph coloring will not be necessary. No prior knowledge of message passing algorithms or belief propagation like techniques will be assumed.
Lukas Kroc is a Ph.D. student in computer science at Cornell University, under the supervision of Professor Bart Selman. His research interests lie in the field of artificial intelligence, especially using techniques from probabilistic reasoning to solve combinatorial problems, such as SAT or model counting.
Ashish Sabharwal is a postdoctoral associate in computer science at Cornell University. He received his Ph.D. from the University of Washington in 2005. He has (co-)authored over 30 publications and surveys, including two best paper awards and four nominations. His research interests include artificial intelligence, automated reasoning (SAT, CSP, QBF), planning, probabilistic inference, complexity, and algorithms.
Bart Selman is a
professor of computer science at Cornell University. He was
previously at AT&T Bell Laboratories. His research interests include
reasoning, planning, knowledge representation, and connections to
statistical physics. He has (co)-authored over 100 publications,
including six best paper awards. He has received the Cornell Miles
Excellence in Teaching Award, the Cornell Outstanding Educator Award,
an NSF Career Award, and a Sloan Research Fellowship. He is a Fellow
of AAAI and of AAAS.
Acknowledgments: This tutorial was funded in part by NSF Award 0713499 (RI: Extending the Reach of SAT Technology --- Quantification, Counting, and Sampling) and NSF EMT Award 0829861 (Collaborative Research: Harnessing Statistical Physics for Computing and Communication).