Walksat stalls well below the satisfiability threshold

Abstract

Partly on the basis of heuristic arguments from physics it has been suggested that the performance of certain types of algorithms on random $k$-SAT formulas is linked to phase transitions that affect the geometry of the set of satisfying assignments. But beyond intuition there has been scant rigorous evidence that "practical" algorithms are affected by these phase transitions. In this paper we prove that \walksat, a popular randomised satisfiability algorithm, fails on random $k$-SAT formulas not very far above clause/variable density where the set of satisfying assignments shatters into tiny, well-separated clusters. Specifically, we prove \walksat\ is ineffective with high probability if $m/n>c{2}^k{\ln }^{2}k/k$, where $m$ is the number of clauses, $n$ is the number of variables and $c>0$ is an absolute constant. By comparison, \walksat\ is known to find satisfying assignments in linear time \whp\ if $m/n<c^{\prime }{2}^k/k$ for another constant $c^{\prime }>0$ [Coja-Oghlan and Frieze, SIAM J.\ Computing 2014].

References in corpus (2)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The large deviations of the whitening process in random constraint satisfaction problems

Cited by in corpus (10)

• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Computational Barriers to Estimation from Low-Degree Polynomials
• Biased landscapes for random Constraint Satisfaction Problems
• Energy landscapes of combinatorial optimization in Ising machines
• The Overlap Gap Property in Principal Submatrix Recovery
• Tractability from overparametrization: The example of the negative perceptron
• Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
• Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion
• Using deep learning to construct stochastic local search SAT solvers with performance bounds
• Interacting Copies of Random Constraint Satisfaction Problems