3 papers
cond-mat.dis-nn2026
Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems
Geri Skenderi, Lorenzo Buffoni, Francesco D'Amico +6
Graph neural networks (GNNs) are increasingly applied to hard optimization problems, often claiming superiority over classical heuristics. However, such claims risk being unsolid d…
cond-mat.dis-nn2025
Algorithmic thresholds in combinatorial optimization depend on the time scaling
M. C. Angelini, M. Avila-González, F. D'Amico +3
In the last decades, many efforts have focused on analyzing typical-case hardness in optimization and inference problems. Some recent work has pointed out that polynomial algorithm…
cond-mat.dis-nn2025
Local equations describe unreasonably efficient stochastic algorithms in random K-SAT
David Machado, Jonathan González-GarcÃa, Roberto Mulet
Despite significant advances in characterizing the highly nonconvex landscapes of constraint satisfaction problems, the good performance of certain algorithms in solving hard combi…