\texttt{WalkSAT} is linear on random 2-SAT

DOI10.1137/24M1718639MaRDI QIDQ6918441zbMATH OpenFDO

Authors Petra Berenbrink, Amin Coja-Oghlan, Colin Cooper, Thorsten Götte, Lukas Hintze, Pavel A. Zakharov

Publication date 10 October 2025

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

Full work available at URL https://doi.org/10.1137/24M1718639

zbMATH Keywords

\texttt{WalkSAT}local searchphase transitionsrandom SAT

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Cites work

• A better algorithm for random \(k\)-SAT
• A threshold for unsatisfiability
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Analyzing Walksat on random formulas
• Differential equations for random processes and random graphs
• 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 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs
• Local search algorithms for SAT: an empirical evaluation
• Lower bounds for random 3-SAT via differential equations
• On smoothed \(k\)-CNF formulas and the \texttt{Walksat} algorithm
• 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 number of random 2-SAT solutions is asymptotically log-normal
• The number of satisfying assignments of random 2‐SAT formulas
• The probabilistic method
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Walksat Stalls Well Below Satisfiability

This page was built for publication: \texttt{WalkSAT} is linear on random 2-SAT

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