11 citations · 32 across the 9 of their papers we have counts for
7 papers · 1 filter
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…
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…
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…
From random point processes to hierarchical Cavity Master Equations for the stochastic dynamics of disordered systems in Random Graphs: Ising models and epidemics
David Machado, Roberto Mulet
We start from the Theory of Random Point Processes to derive n-point coupled master equations describing the continuous dynamics of discrete variables in random graphs. These equat…
The Cavity Master Equation: average and fixed point of the ferromagnetic model in random graphs
E. Domínguez, D. Machado, R. Mulet
The Cavity Master Equation (CME) is a closure scheme to the usual Master Equation representing the dynamics of discrete variables in continuous time. In this work we explore the CM…
A theory of non-equilibrium local search on random satisfaction problems
Erik Aurell, Eduardo Domínguez, David Machado +1
We study local search algorithms to solve instances of the random -satisfiabi lity problem, equivalent to finding (if they exist) zero-energy ground states of statistical models…
Exploring the diluted ferromagnetic p-spin model with a Cavity Master Equation
Erik Aurell, Eduardo Domínguez, David Machado +1
We introduce a new solution to Glauber multi-spin dynamics on random graphs. The solution is based on the recently introduced Cavity Master Equation (CME), a time-closure turning t…