Can I read WalkSAT is linear on random 2-SAT on EtoBox?

WalkSAT is linear on random 2-SAT by Berenbrink, Petra; Coja-Oghlan, Amin; Cooper, Colin; Götte, Thorsten; Hintze, Lukas; Zakharov, Pavel is a scholarly article available to read on EtoBox.

What is WalkSAT is linear on random 2-SAT about?

In an influential article Papadimitriou [FOCS 1991] proved that a local search algorithm called WalkSAT finds a satisfying assignment of a satisfiable 2-CNF with $n$ variables in $O(n^2)$ expected time. Variants of the WalkSAT algorithm have become a mainstay of practical SAT solving (e.g., [Hoos and St\"utzle 2000]). In the present article we analyse the expected running time of WalkSAT on random 2-SAT instances. Answering a question raised by Alekhnovich and Ben-Sasson [SICOMP 2007], we show that WalkSAT runs in linear expected time for all clause/variable densities up to the random 2-SAT satisfiability threshold.

Author

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

Published

2024

Language

EN