467 citations · 4.2k across the 83 of their papers we have counts for
Showing 2004Show all
2 papers · 1 filter
cond-mat.stat-mech2004★ 5 cited
Critical behaviour of combinatorial search algorithms, and the unitary-propagation universality class
Christophe Deroulers, Rémi Monasson
The probability P(alpha, N) that search algorithms for random Satisfiability problems successfully find a solution is studied as a function of the ratio alpha of constraints per va…
cs.DS2004
Heuristic average-case analysis of the backtrack resolution of random 3-Satisfiability instances
Simona Cocco, Remi Monasson
An analysis of the average-case complexity of solving random 3-Satisfiability (SAT) instances with backtrack algorithms is presented. We first interpret previous rigorous works in…