On message passing guided algorithms for solving constraint satisfaction problems

by Guilhem Semerjian

Monday 14 Jul 2008, 14:00 → 16:00 Europe/Rome

Aula Rasetti (Dip. di Fisica - Edificio G. Marconi)

Statistical mechanics studies of optimization problems have found a rich phase diagram for random instances and have led to new efficient heuristics for solving given instances. The theoretical understanding of these new algorithms is not yet completely satisfactory. I will review general ideas about message passing guided algorithms and present new results on the analysis of Belief Propagation