2005

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 »

Statistics of Wave Functions in Disordered Systems with Applications to Coulomb Blockade Peak Spacing

Mike Miller 1, Denis Ullmo 1, 2, Harold U. Baranger 1 Physical Review B 72 (2005) 045305 Despite considerable work on the energy-level and wavefunction statistics of disordered quantum systems, numerical studies of those statistics relevant for electron-electron interactions in mesoscopic systems have been lacking. We plug this gap by using a tight-binding model to study a wide variety of statistics for

Statistics of Wave Functions in Disordered Systems with Applications to Coulomb Blockade Peak Spacing Lire la suite »

Statistics of randomly branched polymers in a semi-space

M. V. Tamm 1, 2, S. K. Nechaev 2, 3, I. Ya. Erukhimovich 1, 4 European Physical Journal E 17 (2005) 209-219 We investigate the statistical properties of a randomly branched 3–functional $N$–link polymer chain without excluded volume, whose one point is fixed at the distance $d$ from the impenetrable surface in a 3–dimensional space. Exactly solving the Dyson-type equation for the partition function

Statistics of randomly branched polymers in a semi-space Lire la suite »

Statistical mechanics of combinatorial optimization problems with site disorder

David S. Dean 1, David Lancaster 2, Satya. N. Majumdar 3 Physical Review E: Statistical, Nonlinear, and Soft Matter Physics 72 (2005) 026125 We study the statistical mechanics of a class of problems whose phase space is the set of permutations of an ensemble of quenched random positions. Specific examples analyzed are the finite temperature traveling salesman problem on several different domains

Statistical mechanics of combinatorial optimization problems with site disorder Lire la suite »

Retour en haut