Walksat stalls well below the satisfiability threshold

Amin Coja-Oghlan, Amir Haqshenas, Samuel Hetterich

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