24 citations · 40 across the 9 of their papers we have counts for
9 papers
Collision Resistance of Single-Layer Neural Nets
Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta +5
We initiate the study of the algorithmic complexity of finding collisions in single-layer binary neural networks. Given a random matrix , an…
Are Neural Networks Collision Resistant?
Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta +5
When neural networks are trained to classify a dataset, one finds a set of weights from which the network produces a label for each data point. We study the algorithmic complexity…
Overlap Gap and Computational Thresholds in the Square Wave Perceptron
Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta +5
Square Wave Perceptrons (SWPs) form a class of neural network models with oscillating activation function that exhibit intriguing ``hardness'' properties in the high-dimensional li…
Solution of the Critical Dynamics of the Mean-Field Kob-Andersen Model
Gianmarco Perrupato, Tommaso Rizzo
We analytically solve the critical dynamics of the Kob-Andersen kinetically constrained model of supercooled liquids on the Bethe lattice, employing a combinatorial argument based…
Thermodynamics of the Fredrickson-Andersen Model on the Bethe Lattice
Gianmarco Perrupato, Tommaso Rizzo
The statics of the Fredrickson-Andersen model (FAM) of the liquid-glass transition is solved on the Bethe lattice (BL). The kinetic constraints of the FAM imply on the BL an ergodi…
Theory of Kinetically-Constrained-Models Dynamics
Gianmarco Perrupato, Tommaso Rizzo
The mean-field theory of Kinetically-Constrained-Models is developed by considering the Fredrickson-Andersen model on the Bethe lattice. Using certain properties of the dynamics ob…
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…
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…
Random-link matching problems on random regular graphs
Giorgio Parisi, Gianmarco Perrupato, Gabriele Sicuro
We study the random-link matching problem on random regular graphs, alongside with two relaxed versions of the problem, namely the fractional matching and the so-called "loopy" fra…