Journal
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT
Volume -, Issue -, Pages -Publisher
IOP PUBLISHING LTD
DOI: 10.1088/1742-5468/2009/09/P09001
Keywords
cavity and replica method; analysis of algorithms; message-passing algorithms
Categories
Ask authors/readers for more resources
We introduce a version of the cavity method for diluted mean field spin models that allows the computation of thermodynamic quantities similar to the Franz-Parisi quenched potential in sparse random graph models. This method is developed in the particular case of partially decimated random constraint satisfaction problems. This allows us to develop a theoretical understanding of a class of algorithms for solving constraint satisfaction problems, in which elementary degrees of freedom are sequentially assigned according to the results of a message passing procedure (belief propagation). We confront this theoretical analysis with the results of extensive numerical simulations.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available