Walksat Stalls Well Below Satisfiability

DOI10.1137/16M1084158MaRDI QIDQ5267998zbMATH OpenFDO

Authors Amin Coja-Oghlan, A. Haqshenas, Samuel Hetterich

Publication date 14 June 2017

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.00346

zbMATH Keywords

random \(k\)-SATWalksat

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20)

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}l{n}^{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].

Recommendations

• Stuck walks
• Auto-Walksat: A self-tuning implementation of Walksat
• Self-avoiding walks
• Analyzing Walksat on random formulas
• Analyzing Walksat on random formulas
• Weak saturation stability
• From vicious walkers to TASEP
• On the Unreasonable Effectiveness of SAT Solvers
• Absorbing random walks and the NAE2SAT problem
• Absorbing Random Walks and the NAE2SAT Problem

Cites work

• 3-SAT faster and simpler -- unique-SAT bounds for PPSZ hold in general
• A better algorithm for random \(k\)-SAT
• An improved exponential-time algorithm for k -SAT
• Analysing survey propagation guided decimationon random formulas
• Analyzing Walksat on random formulas
• Cores in random hypergraphs and Boolean formulas
• Exponential bounds for DPLL below the satisfiability threshold
• Frozen variables in random Boolean constraint satisfaction problems
• Gibbs states and the set of solutions of random constraint satisfaction problems
• scientific article; zbMATH DE number 437557 (Why is no real title available?)
• scientific article; zbMATH DE number 67483 (Why is no real title available?)
• scientific article; zbMATH DE number 1246226 (Why is no real title available?)
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 2086385 (Why is no real title available?)
• scientific article; zbMATH DE number 6469161 (Why is no real title available?)
• Improving PPSZ for 3-SAT using critical variables
• Limits of local algorithms over sparse random graphs
• Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs
• Local algorithms for independent sets are half-optimal
• On belief propagation guided decimation for random k-SAT
• On the solution-space geometry of random constraint satisfaction problems
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• Proof of the satisfiability conjecture for large k
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• The asymptotic k-SAT threshold
• The large deviations of the whitening process in random constraint satisfaction problems
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing

Cited in

(29)

• The overlap gap property in principal submatrix recovery
• Optimal low-degree hardness of maximum independent set
• Computational barriers to estimation from low-degree polynomials
• The overlap gap property and approximate message passing algorithms for \(p\)-spin models
• Analyzing Walksat on random formulas
• Performance of sequential local algorithms for the random NAE-K-SAT problem
• Pushing Random Walk Beyond Golden Ratio
• Impurity: another phase transition of SAT
• scientific article; zbMATH DE number 1737509 (Why is no real title available?)
• On smoothed \(k\)-CNF formulas and the \texttt{Walksat} algorithm
• Biased landscapes for random constraint satisfaction problems
• Decoding from pooled data: sharp information-theoretic bounds
• Counting solutions to random CNF formulas
• Analyzing Walksat on random formulas
• Theory and Applications of Satisfiability Testing
• Convergence of warning propagation algorithms for random satisfiable instances
• Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs
• Theory and Applications of Satisfiability Testing
• scientific article; zbMATH DE number 2243408 (Why is no real title available?)
• Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion
• Free Energy Wells and Overlap Gap Property in Sparse PCA
• Tractability from overparametrization: the example of the negative perceptron
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics
• The landscape of the planted clique problem: dense subgraphs and the overlap gap property
• The low-degree hardness of finding large independent sets in sparse random hypergraphs
• Counting solutions to random CNF formulas
• \texttt{WalkSAT} is linear on random 2-SAT
• Sharp phase transitions for the overlap gap property
• Sharp thresholds for the overlap gap property: Ising p-spin Glass and random k-SAT

This page was built for publication: Walksat Stalls Well Below Satisfiability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5267998)