DIMACS Working Group on Message-Passing Algorithms

October 13 - 17, 2008
DIMACS Center, CoRE Building, Rutgers University

Riccardo Zecchina, International Centre for Theoretical Physics (ICTP), riccardo.zecchina at polito.it
Gregory Sorkin, IBM Research, sorkin at watson.ibm.com
Presented under the auspices of the Special Focus on Discrete Random Systems.

This working group will focus on the impact of heuristic approaches and algorithms from physics on mathematics and computer science. Particular attention will be devoted to message-passing techniques such as Belief Propagation and Survey Propagation, which have shown amazing performance as solvers for random constraint satisfaction problems (K-satisfiability, Q-coloring, and matching, to mention just a few). The goals of the workshop include promulgating these techniques, extending the scope of mathematical rigor systematically or ad hoc, and subjecting physically derived conjectures and algorithms to rigorous scrutiny. The techniques are of interest in fields including physics (disordered systems), information theory (source coding and inference), computer science (optimization), and computational biology (network reconstruction).

Next: Call for Participation
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on May 9, 2008.