When Does Hillclimbing Fail on Monotone Functions: An entropy compression argument

Johannes Lengler, Anders Martinsson, Angelika Steger

Hillclimbing is an essential part of any optimization algorithm. An important benchmark for hillclimbing algorithms on pseudo-Boolean functions $f:\{0,1{\}}^n\to \mathbb{R}$ are (s…