226 citations · 649 across the 15 of their papers we have counts for
3 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…