Combinatorics Seminar

When: Sunday, December 12, 10am Where: Schreiber 309 Speaker: Amin Coja-Oghlan, University of Warwick Title: On Belief Propagation Guided Decimation for random k-SAT

Abstract:

Random k-SAT instances are challenging benchmarks for SAT-solving algorithms. Physicists have put forward an algorithm called Belief Propagation guided decimation that harnesses the Belief Propagation technique from AI in order to construct satisfying assignments. Experiments indicate that this algorithm far outperforms other SAT solvers such as Walksat or zChaff for k=3,4,5. I am going to present the first rigorous analysis of BP guided decimation, showing that for larger k (the basic version of) this algorithm does not outperform other, simpler ones.