Laboratoire de Physique Théorique et Modèles Statistiques

Séminaire commun LPT-LPTMS : Petr Sulc

Belief propagation for graph partitioning

Petr Sulc, Los Alamos National Laboratory

We study the belief propagation algorithm for the graph bi-partitioning problem, i.e. the ground state of the ferromagnetic Ising model at a fixed magnetization. Application of a message passing scheme to a model with a fixed global parameter is not banal and we show that the magnetization can in fact be fixed in a local way within the belief propagation equations. Our method provides the full phase diagram of the bi-partitioning problem on random graphs, as well as an efficient heuristic solver that we anticipate to be useful in a wide range of application of the partitioning problem.
Work done in collaboration with L. Zdeborova

Jeudi 3 juin à 14h

LPTMS-batiment 100, salle 201, Orsay


Calendrier des séminaires

Mai
Juillet
Juin 2010
lun. mar. mer. jeu. ven.
 
1
16:00» Seminaire LPTMS: Uzy Smilansky (Weizmann)
2
3
14:00» Séminaire commun LPT-LPTMS : Petr Sulc
4
11:00» Séminaire du LPTMS : Yoshiyuki Kabashima
7
14:00» Séminaire PHYSTAT-SUD : Jon Keating
8
11:00» Seminaire LPTMS : Luigi Cantini (LPT ENS)
9
10
11
14
15
11:00» Seminaire LPTMS: Rhoda Hawkins
16
17
18
14:00» Séminaire Physique Biologique et Systèmes Complexes : Guillaume Romet-Lemonne
21
22
11:00» Semianire LPTMS: Martin Lenz (Chicago)
23
24
16:00» Séminaire du LPTMS : Gunnar Boldhaus
25
10:30» Soutenance de thèse : Carlos Eduardo Alvarez Cabrera
15:00» Séminaire exceptionnel du LPTMS : Paolo Solinas
28
29
11:00» Seminaire LPTMS: Celine Nadal, Alvaro Rojo
30