7 papers
Critical exponents of the spin glass transition in a field at zero temperature
Maria Chiara Angelini, Saverio Palazzi, Giorgio Parisi +1
We analyze the spin glass transition in a field in finite dimension below the upper critical dimension directly at zero temperature using a recently introduced perturbative loo…
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…
Long-range spin glass in a field at zero temperature
Maria Chiara Angelini, Saverio Palazzi, Giorgio Parisi +1
We compute the critical exponents of the zero-temperature spin glass transition in a field on a one-dimensional long-range model, a proxy for higher-dimensional systems. Our approa…
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…
Interacting Copies of Random Constraint Satisfaction Problems
Maria Chiara Angelini, Louise Budzynski, Federico Ricci-Tersenghi
We study a system of coupled copies of a well-known constraint satisfaction problem (random hypergraph bicoloring) to examine how the ferromagnetic coupling between the copie…
Bethe -layer construction for the percolation problem
Maria Chiara Angelini, Saverio Palazzi, Tommaso Rizzo +1
The major difference between percolation and other phase transition models is the absence of an Hamiltonian and of a partition function. For this reason it is not straightforward t…