467 citations · 4.2k across the 83 of their papers we have counts for
5 papers · 1 filter
A review of the Statistical Mechanics approach to Random Optimization Problems
Fabrizio Altarelli, Remi Monasson, Guilhem Semerjian +1
We review the connection between statistical mechanics and the analysis of random optimization problems, with particular emphasis on the random k-SAT problem. We discuss and charac…
Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions
Fabrizio Altarelli, Remi Monasson, Francesco Zamponi
We study the performances of stochastic heuristic search algorithms on Uniquely Extendible Constraint Satisfaction Problems with random inputs. We show that, for any heuristic pres…
Can rare SAT formulas be easily recognized? On the efficiency of message passing algorithms for K-SAT at large clause-to-variable ratios
Fabrizio Altarelli, Remi Monasson, Francesco Zamponi
For large clause-to-variable ratio, typical K-SAT instances drawn from the uniform distribution have no solution. We argue, based on statistical mechanics calculations using the re…
A generating function method for the average-case analysis of DPLL
Remi Monasson
A method to calculate the average size of Davis-Putnam-Loveland-Logemann (DPLL) search trees for random computational problems is introduced, and applied to the satisfiability of r…
Approximate analysis of search algorithms with "physical" methods
Simona Cocco, Remi Monasson, Andrea Montanari +1
An overview of some methods of statistical physics applied to the analysis of algorithms for optimization problems (satisfiability of Boolean constraints, vertex cover of graphs, d…