BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Belief propagation guided decimation for random k-SAT - Amin Coja-
 Oghlan (University of Warwick)
DTSTART:20110602T133000Z
DTEND:20110602T143000Z
UID:TALK30110@talks.cam.ac.uk
CONTACT:Andrew Thomason
DESCRIPTION:Let F be a uniformly distributed random k-SAT formula with n v
 ariables and m clauses. Non-constructive arguments show that F is satisfia
 ble for clause/variable ratios m/n< r(k)~2^k ln 2 with high probability. Y
 et no efficient algorithm is know to find a satisfying assignment for dens
 ities as low as m/n~r(k).ln(k)/k with a non-vanishing probability. In fact
 \, the density m/n~r(k).ln(k)/k seems to form a barrier for a broad class 
 of local search algorithms. One of the very few algorithms that plausibly 
 seemed capable of breaking this barrier is a message passing algorithm cal
 led Belief Propagation Guided Decimation. It was put forward on the basis 
 of deep but non-rigorous statistical mechanics considerations. Experiments
  conducted for k=3\,4\,5 suggested that the algorithm might succeed for de
 nsities very close to r_k. In this talk I'm going to sketch a rigorous ana
 lysis of this algorithm\, showing that (in its simplest version) it fails 
 to find a satisfying assignment already for m/n>c.r(k)/k\, for a constant 
 c>0 independent of k.\n
LOCATION:MR12
END:VEVENT
END:VCALENDAR