5 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…
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…
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…
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…
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…