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.

On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms / RICCI TERSENGHI, Federico; Guilhem, Semerjian. - In: JOURNAL OF STATISTICAL MECHANICS: THEORY AND EXPERIMENT. - ISSN 1742-5468. - 2009:9(2009), pp. P09001--. [10.1088/1742-5468/2009/09/p09001]

On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms

RICCI TERSENGHI, Federico;
2009

Abstract

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.
2009
analysis of algorithms; cavity and replica method; message-passing algorithms
01 Pubblicazione su rivista::01a Articolo in rivista
On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms / RICCI TERSENGHI, Federico; Guilhem, Semerjian. - In: JOURNAL OF STATISTICAL MECHANICS: THEORY AND EXPERIMENT. - ISSN 1742-5468. - 2009:9(2009), pp. P09001--. [10.1088/1742-5468/2009/09/p09001]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/131320
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 48
  • ???jsp.display-item.citation.isi??? 40
social impact