Phase transition for Local Search on planted SAT

Andrei A. Bulatov, Evgeny S. Skvortsov

The Local Search algorithm (or Hill Climbing, or Iterative Improvement) is one of the simplest heuristics to solve the Satisfiability and Max-Satisfiability problems. It is a part…