publications

The statistical mechanics of traveling salesman type problems

David S. Dean 1, 2, David Lancaster 3, Satya Majumdar 4 Journal of Statistical Mechanics: Theory and Experiment 1 (2005) L01001 We study the finite temperature statistical mechanics of Hamiltonian paths between a set of N quenched randomly distributed points in a finite domain D. The energy of the path is a function of the distance between neighboring points on the path, an […]

The statistical mechanics of traveling salesman type problems Lire la suite »

The cavity method for large deviations

Olivier Rivoire 1 Journal of Statistical Mechanics: Theory and Experiment 1 (2005) P04007 A method is introduced for studying large deviations in the context of statistical physics of disordered systems. The approach, based on an extension of the cavity method to atypical realizations of the quenched disorder, allows us to compute exponentially small probabilities (rate functions) over

The cavity method for large deviations Lire la suite »

Survey-propagation decimation through distributed local computations

Joel Chavas 1, Cyril Furtlehner 2, Marc Mezard 2, Riccardo Zecchina 3 Journal of Statistical Mechanics: Theory and Experiment P (2005) P11016 We discuss the implementation of two distributed solvers of the random K-SAT problem, based on some development of the recently introduced survey-propagation (SP) algorithm. The first solver, called the \’SP diffusion algorithm\’, diffuses as dynamical information the maximum bias over the

Survey-propagation decimation through distributed local computations Lire la suite »

Survey propagation: an algorithm for satisfiability

A. Braunstein 1, 2, M. Mezard 3, R. Zecchina 2 Random Structures and Algorithms 27 (2005) 201-226 We study the satisfiability of randomly generated formulas formed by $M$ clauses of exactly $K$ literals over $N$ Boolean variables. For a given value of $N$ the problem is known to be most difficult with $\\alpha=M/N$ close to the experimental threshold $\\alpha_c$ separating the region

Survey propagation: an algorithm for satisfiability Lire la suite »

Retour en haut