Everything about WalkSAT

🧭 Start here: a 6-step reading path

1. Read the overview: WalkSATA 5-minute orientation
2. Skim a recent paper: WalkSAT is Linear on Random 2-SATInfluential work since 2022
3. Read the landmark paper: Walksat Stalls Well Below SatisfiabilityCited 24 times
4. Go sideways: Boolean satisfiability algorithm heuristicsA closely related topic
5. Go sideways: Boolean satisfiability problemA closely related topic

🏆 Landmark papers (most cited)

• Walksat Stalls Well Below Satisfiability

  A. Coja-Oghlan, A. Haqshenas, S. Hetterich · 2017 · SIAM Journal on Discrete Mathematics · 24 citations

• Auto-Walksat: A Self-Tuning Implementation of Walksat

  Donald J. Patterson, Henry Kautz · 2001 · Electronic Notes in Discrete Mathematics · 22 citations

• Complexity of several constraint-satisfaction problems using the heuristic classical algorithm WalkSAT

  Marco Guidetti, A. P. Young · 2011 · Physical Review E · 19 citations

• Improving WalkSAT By Effective Tie-Breaking and Efficient Implementation

  Shaowei Cai, Chuan Luo, Kaile Su · 2014 · The Computer Journal · 14 citations

• Analyzing Walksat on Random Formulas

  Amin Coja-Oghlan, Alan Frieze · 2014 · SIAM Journal on Computing · 12 citations

• Planning as Propositional CSP: From Walksat to Local Search Techniques for Action Graphs

  Alfonso Gerevini, Ivan Serina · 2003 · Constraints · 12 citations

• A Variable Neighborhood Walksat-Based Algorithm for MAX-SAT Problems

  Noureddine Bouhmala · 2014 · The Scientific World Journal · 8 citations

• Improving WalkSAT for Random k-Satisfiability Problem with k > 3

  Shaowei Cai, Kaile Su, Chuan Luo · 2013 · Proceedings of the AAAI Conference on Artificial Intelligence · 8 citations

🆕 Influential since 2022

• WalkSAT is Linear on Random 2-SAT

  Petra Berenbrink, Amin Coja-Oghlan, Colin Cooper · 2025 · SIAM Journal on Discrete Mathematics · 1 citations

• A 28-nm Mixed-Signal Hybrid SAT Solver With Continuous-Time Convergence and WalkSAT-Inspired Discrete Variable Flips

  Yuyao Kong, Haomei Liu, Jianwei Jia · 2026 · IEEE Solid-State Circuits Letters · 0 citations

• Interactive particle systems on hypergraphs, drift analysis and the WalkSAT algorithm

  Gabriel Istrate, Cosmin Bonchiş, Mircea Marin · 2027 · Journal of Complexity · 0 citations

• Separation between WalkSAT and DPLL

  Tao Jiang, Shaowei Cai, Ziqun Li · 2026 · Theoretical Computer Science · 0 citations

📚 Books worth reading

Open Library didn't respond; try again in a moment.

🔗 Related topics

• Boolean satisfiability algorithm heuristics In computer science, there are certain classes of algorithms (heuristics) that solves types of the Boolean satisfiability problem despite there being no…
• Boolean satisfiability problem In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY…
• Satplan Satplan (better known as Planning as Satisfiability) is a method for automated planning. It converts the planning problem instance into an instance of…
• Maximum satisfiability problem In computational complexity theory, the maximum satisfiability problem (MAX-SAT) is the problem of determining the maximum number of clauses, of a given…
• SAT solver In computer science and formal methods, a SAT solver is a computer program which aims to solve the Boolean satisfiability problem (SAT). On input a formula…
• MAXEkSAT MAXEkSAT is a problem in computational complexity theory that is a maximization version of the Boolean satisfiability problem 3SAT. In MAXEkSAT, each clause…
• Algorithm selection Algorithm selection (sometimes also called per-instance algorithm selection or offline algorithm selection) is a meta-algorithmic technique to choose an…
• DPLL algorithm In logic and computer science, the Davis–Putnam–Logemann–Loveland (DPLL) algorithm is a complete, backtracking-based search algorithm for deciding the…