What is it about?
Some algorithms can unexpectedly solve typical instances of hard problems. Understanding why and how this happens remains an open question in several fields, from cryptography to machine learning. We provide the first equations that accurately predict the limits of state-of-the-art local search algorithms on hard combinatorial optimization. Our technique can also be recast as another efficient algorithm capable of finding solutions in unexpected scenarios.
Featured Image
Photo by BoliviaInteligente on Unsplash
Why is it important?
We reproduce, for the first time, several qualitative and quantitative aspects of the algorithmic dynamics with deterministic equations. Since we consider only local correlations, the solution space explored by the algorithm has a simple structure, as suggested by previous observations.
Perspectives
The accuracy and interpretability of the equations open paths to detailed studies of the space of solutions and to understanding the links between its properties and the true onset of hardness in those problems. The theory can be directly applied to different hard problems with little effort. Furthermore, we propose a flexible new algorithm whose hyperparameters can be optimized to efficiently solve more instances of these problems.
David Machado Pérez
Universita degli Studi di Roma La Sapienza
Read the Original
This page is a summary of: Local equations describe unreasonably efficient stochastic algorithms in random K-SAT, Proceedings of the National Academy of Sciences, December 2025, Proceedings of the National Academy of Sciences,
DOI: 10.1073/pnas.2510153122.
You can read the full text:
Resources
Contributors
The following have contributed to this page
