WalkSAT is linear on random 2-SAT

Petra Berenbrink, Amin Coja-Oghlan, Colin Cooper +3

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 $…