BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Combinatorics Seminar
SUMMARY:Belief propagation guided decimation for random k-
SAT - Amin Coja-Oghlan (University of Warwick)
DTSTART;TZID=Europe/London:20110602T143000
DTEND;TZID=Europe/London:20110602T153000
UID:TALK30110AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/30110
DESCRIPTION:Let F be a uniformly distributed random k-SAT form
ula with n variables and m clauses. Non-constructi
ve arguments show that F is satisfiable for clause
/variable ratios m/n< r(k)~2^k ln 2 with high prob
ability. Yet no efficient algorithm is know to fin
d a satisfying assignment for densities 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 f
orm a barrier for a broad class of local search al
gorithms. One of the very few algorithms that plau
sibly seemed capable of breaking this barrier is a
message passing algorithm called Belief Propagati
on Guided Decimation. It was put forward on the ba
sis of deep but non-rigorous statistical mechanics
considerations. Experiments conducted for k=3\,4\
,5 suggested that the algorithm might succeed for
densities very close to r_k. In this talk I'm goin
g to sketch a rigorous analysis 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
CONTACT:Andrew Thomason
END:VEVENT
END:VCALENDAR