Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions

We study the performances of stochastic heuristic search algorithms on Uniquely Extendible Constraint Satisfaction Problems with random inputs. We show that, for any heuristic preserving the Poissonian nature of the underlying instance, the (heuristic-dependent) largest ratio αa of constraints per variables for which a search algorithm is likely to find solutions is smaller than the critical ratio αd above which solutions are clustered and highly correlated. In addition we show that the clustering ratio can be reached when the number k of variables per constraints goes to infinity by the so-called Generalized Unit Clause heuristic.

• Publication year

  2007

• Venue

  arXiv.org

• Publication date

  2007-09-04

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1088/1742-6596/95/1/012013arXiv 0709.0367
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Phase diagram of the 1-in-3 satisfiability problem.

  2007cited by this paper
• On the Freezing of Variables in Random Constraint Satisfaction Problems

  2007cited by this paper
• A Landscape Analysis of Constraint Satisfaction Problems

  2007cited by this paper
• Introduction to Phase Transitions in Random Optimization Problems

  2007cited by this paper
• Gibbs states and the set of solutions of random constraint satisfaction problems

  2006cited by this paper
• On the Dynamics of the Glass Transition on Bethe Lattices

  2005cited by this paper
• A Random Constraint Satisfaction Problem That Seems Hard for DPLL

  2004cited by this paper
• A sharp threshold in proof complexity yields lower bounds for satisfiability search

  2004cited by this paper
• Two Solutions to Diluted p-Spin Models and XORSAT Problems

  2003cited by this paper
• Dynamics of heuristic optimization algorithms on random graphs

  2002cited by this paper
• Rigorous decimation-based construction of ground pure states for spin-glass models on random lattices.

  2002cited by this paper
• The 3-XORSAT threshold

  2002cited by this paper
• Lower bounds for random 3-SAT via differential equations

  2001cited by this paper
• THE EUROPEAN PHYSICAL JOURNAL B c○ EDP Sciences

  2000cited by this paper
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k satisfiability problem

  1990cited by this paper
• Spin Glass Theory and Beyond

  1987cited by this paper
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem

  1986cited by this paper

• Roadblocks and Opportunities in Quantum Algorithms -- Insights from the National Quantum Initiative Joint Algorithms Workshop, May 20--22, 2024

  2025cites this paper
• Entropic barriers as a reason for hardness in both classical and quantum algorithms

  2021cites this paper
• Interactive Particle Systems on Hypergraphs, Drift Analysis and the WalkSAT algorithm

  2019cites this paper
• Mean-field disordered systems : glasses and optimization problems, classical and quantum

  2013cites this paper
• Appendix A: Symbols and Notations

  2012cites this paper
• The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem

  2012cites this paper
• Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT

  2012cites this paper
• Generalized Survey Propagation

  2011cites this paper
• Typical rank of coin-toss power-law random matrices over GF(2)

  2010cites this paper
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms

  2009cites this paper
• Threshold Phenomena in Random Constraint Satisfaction Problems

  2008cites this paper
• Theoretical analysis of optimization problems - Some properties of random k-SAT and k-XORSAT

  2008cites this paper
• Is SP BP

  2007cites this paper