Despite relevant advances in the characterization of highly non-convex landscapes, the unreasonably good performance of some local search algorithms in solving hard combinatorial optimization tasks is still not understood. Part of the difficulty lies in the absence of theoretical tools to study dynamics completely out-of-equilibrium. In this context, we extend a system of approximated master equations, the Conditional Dynamic Approximation (CDA), to describe local search algorithms in the random K-SAT problem. In our numerical experiments with 3-SAT, we get a qualitative agreement with the phase diagrams of two emblematic examples: Focused Metropolis Search (FMS) and greedy-WalkSAT. The CDA is the only available technique that predicts the algorithmic threshold of FMS beyond the clustering transition of random 3-SAT. Moreover, we transform the results of these approximate equations into actual solutions using decimation, showing that CDA gets information about the local structure of actual solutions. This CDA-guided decimation also achieves an algorithmic threshold beyond the clustering transition, outperforming similar schemes like Belief Propagation-guided decimation. The results suggest that long-range correlations are not necessary to describe the dynamics of some efficient local search algorithms. The CDA, as presented here, is directly applicable to other hard combinatorial optimization problems in sparse random graphs.

Biography

Prof. Roberto Mulet works at the Center for Complex Systems and at the Department of Theoretical Physics of the University of Havana. His research work is concentrated on Statistical Physics, Soft Matter, Biological Physics, Nonlinear Dynamics and Theoretical Physics.

Inviter: Hai-Jun Zhou