A New Perspective on Stochastic Local Search and the Lovasz Local Lemma.
Dimitris Achlioptas, Fotis Iliopoulos, Alistair Sinclair · arXiv (Cornell University) · 2018
We present a new perspective on the analysis of stochastic local search algorithms via linear algebra. Our key insight is that LLL-inspired convergence arguments can be seen as a method for bounding the spectral radius of a matrix specifying the algorithm to be analyzed. Armed with this viewpoint we give a unified analysis of all \emph{entropy compression} applications, connecting backtracking algorithms to the LLL in the same fashion that existing analyses connect resampling algorithms to the LLL. We then give a new convergence condition that seamlessly handles resampling algorithms that can detect, and back away from, unfavorable parts of the state space. We give several applications of this condition, notably a new vertex coloring algorithm for arbitrary graphs that uses a number of colors that matches the algorithmic barrier for random graphs. Finally, we introduce a generalization of Kolmogorov's notion of \emph{commutative} algorithms, cast as matrix commutativity, which affords much simpler proofs both of the original results and of recent extensions.