110 citations · 471 across the 28 of their papers we have counts for
28 papers
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…
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…
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…
Bethe -layer construction on the Ising model
Maria Chiara Angelini, Saverio Palazzi, Giorgio Parisi +1
In statistical physics, one of the standard methods to study second order phase transitions is the renormalization group that usually leads to an expansion around the corresponding…
Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problems
Maria Chiara Angelini, Angelo Giorgio Cavaliere, Raffaele Marino +1
Is Stochastic Gradient Descent (SGD) substantially different from Metropolis Monte Carlo dynamics? This is a fundamental question at the time of understanding the most used trainin…
Real-Space Renormalization group for spin glasses
Maria Chiara Angelini
While in the fully-connected limit the solution of the spin-glass model is known, with the existence of a complex transition on a critical line in the temperature-external field ph…
The Ising spin glass on random graphs at zero temperature: not all spins are glassy in the glassy phase
Gianmarco Perrupato, Maria Chiara Angelini, Giorgio Parisi +2
We investigate the replica symmetry broken (RSB) phase of spin glass (SG) models in a random field defined on Bethe lattices at zero temperature. From the properties of the RSB sol…
Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set
Maria Chiara Angelini, Federico Ricci-Tersenghi
The recent work ``Combinatorial Optimization with Physics-Inspired Graph Neural Networks'' [Nat Mach Intell 4 (2022) 367] introduces a physics-inspired unsupervised Graph Neural Ne…
Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
Maria Chiara Angelini, Federico Ricci-Tersenghi
The planted coloring problem is a prototypical inference problem for which thresholds for Bayes optimal algorithms, like Belief Propagation (BP), can be computed analytically. In t…
Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model
Maria Chiara Angelini, Paolo Fachin, Simone de Feo
Over-parametrization was a crucial ingredient for recent developments in inference and machine-learning fields. However a good theory explaining this success is still lacking. In t…
Unexpected upper critical dimension for spin glass models in a field predicted by the loop expansion around the Bethe solution at zero temperature
Maria Chiara Angelini, Carlo Lucibello, Giorgio Parisi +3
The spin-glass transition in a field in finite dimension is analyzed directly at zero temperature using a perturbative loop expansion around the Bethe lattice solution. The loop ex…
Solving the fully-connected spherical -spin model with the cavity method: equivalence with the replica results
Giacomo Gradenigo, Maria Chiara Angelini, Luca Leuzzi +1
The spherical -spin is a fundamental model for glassy physics, thanks to its analytic solution achievable via the replica method. Unfortunately the replica method has some drawb…
Comment on "Real-space renormalization-group methods for hierarchical spin glasses"
Maria Chiara Angelini, Giorgio Parisi, Federico Ricci-Tersenghi
In the paper [Angelini M C, Parisi G, and Ricci-Tersenghi F, Ensemble renormalization group for disordered systems, Phys. Rev. B 87 134201 (2013)] we introduced a real-space renorm…
New loop expansion for the Random Magnetic Field Ising Ferromagnets at zero temperature
Maria Chiara Angelini, Carlo Lucibello, Giorgio Parisi +2
We apply to the Random Field Ising Model at zero temperature (T= 0) the perturbative loop expansion around the Bethe solution. A comparison with the standard epsilon-expansion is m…
Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
Maria Chiara Angelini, Federico Ricci-Tersenghi
The effectiveness of stochastic algorithms based on Monte Carlo dynamics in solving hard optimization problems is mostly unknown. Beyond the basic statement that at a dynamical pha…
Parallel Tempering for the planted clique problem
Maria Chiara Angelini
The theoretical information threshold for the planted clique problem is , however no polynomial algorithm is known to recover a planted clique of size , $…
Loop expansion around the Bethe approximation through the -layer construction
Ada Altieri, Maria Chiara Angelini, Carlo Lucibello +3
For every physical model defined on a generic graph or factor graph, the Bethe -layer construction allows building a different model for which the Bethe approximation is exact i…
Real Space Migdal-Kadanoff Renormalisation of Glassy Systems: Recent Results and a Critical Assessment
Maria Chiara Angelini, Giulio Biroli
In this manuscript, in honour of L. Kadanoff, we present recent progress obtained in the description of finite dimensional glassy systems thanks to the Migdal-Kadanoff renormalisat…
Real Space Renormalization Group Theory of Disordered Models of Glasses
Maria Chiara Angelini, Giulio Biroli
We develop a real space renormalisation group analysis of disordered models of glasses, in particular of the spin models at the origin of the Random First Order Transition theory.…
Spectral Detection on Sparse Hypergraphs
Maria Chiara Angelini, Francesco Caltagirone, Florent Krzakala +1
We consider the problem of the assignment of nodes into communities from a set of hyperedges, where every hyperedge is a noisy observation of the community assignment of the adjace…
Spin Glass in a Field: a New Zero-Temperature Fixed Point in Finite Dimensions
Maria Chiara Angelini, Giulio Biroli
By using real space renormalisation group (RG) methods we show that spin-glasses in a field display a new kind of transition in high dimensions. The corresponding critical properti…