Physics – Condensed Matter – Disordered Systems and Neural Networks
Scientific paper
2009-04-22
J Stat. Mech. P09001 (2009)
Physics
Condensed Matter
Disordered Systems and Neural Networks
32 pages, 24 figures
Scientific paper
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 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 to the results of extensive numerical simulations.
Ricci-Tersenghi Federico
Semerjian Guilhem
No associations
LandOfFree
On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-274863