304 citations · 2.4k across the 61 of their papers we have counts for
15 papers · 1 filter
Evidence of Replica Symmetry Breaking under the Nishimori conditions in epidemic inference on graphs
Alfredo Braunstein, Louise Budzynski, Matteo Mariani +1
In Bayesian inference, computing the posterior distribution from the data is typically a non-trivial problem, which usually requires approximations such as mean-field approaches or…
Small-Coupling Dynamic Cavity: a Bayesian mean-field framework for epidemic inference
Alfredo Braunstein, Giovanni Catania, Luca Dall'Asta +3
We present the Small-Coupling Dynamic Cavity (SCDC) method, a novel generalized mean-field approximation for epidemic inference and risk assessment within a fully Bayesian framewor…
The cavity method: from exact solutions to algorithms
Alfredo Braunstein, Guilhem Semerjian
The goal of this chapter is to review the main ideas that underlie the cavity method for disordered models defined on random graphs, as well as present some of its outcomes, focusi…
The closest vector problem and the zero-temperature p-spin landscape for lossy compression
Alfredo Braunstein, Louise Budzynski, Stefano Crotti +1
We consider a high-dimensional random constrained optimization problem in which a set of binary variables is subjected to a linear system of equations. The cost function is a simpl…
The large deviations of the whitening process in random constraint satisfaction problems
Alfredo Braunstein, Luca Dall'Asta, Guilhem Semerjian +1
Random constraint satisfaction problems undergo several phase transitions as the ratio between the number of constraints and the number of variables is varied. When this ratio exce…
A Max-Sum algorithm for training discrete neural networks
Carlo Baldassi, Alfredo Braunstein
We present an efficient learning algorithm for the problem of training neural networks with discrete synapses, a well-known hard (NP-complete) discrete optimization problem. The al…
The edge-disjoint path problem on random graphs by message-passing
Fabrizio Altarelli, Alfredo Braunstein, Luca Dall'Asta +2
We present a message-passing algorithm to solve the edge disjoint path problem (EDP) on graphs incorporating under a unique framework both traffic optimization and path length mini…
Theory and learning protocols for the material tempotron model
Carlo Baldassi, Alfredo Braunstein, Riccardo Zecchina
Neural networks are able to extract information from the timing of spikes. Here we provide new results on the behavior of the simplest neuronal model which is able to decode inform…
Optimizing spread dynamics on graphs by message passing
Fabrizio Altarelli, Alfredo Braunstein, Luca Dall'Asta +1
Cascade processes are responsible for many important phenomena in natural and social sciences. Simple models of irreversible dynamics on graphs, in which nodes activate depending o…
Clustering with shallow trees
M. Bailly-Bechet, S. Bradde, A. Braunstein +3
We propose a new method for hierarchical clustering based on the optimisation of a cost function over trees of limited depth, and we derive a message--passing method that allows to…
Learning by message-passing in networks of discrete synapses
Alfredo Braunstein, Riccardo Zecchina
We show that a message-passing process allows to store in binary "material" synapses a number of random patterns which almost saturates the information theoretic bounds. We apply t…
Source coding by efficient selection of ground states clusters
Demian Battaglia, Alfredo Braunstein, Joël Chavas +1
In this letter, we show how the Survey Propagation algorithm can be generalized to include external forcing messages, and used to address selectively an exponential number of glass…
Survey Propagation as local equilibrium equations
A. Braunstein, R. Zecchina
It has been shown experimentally that a decimation algorithm based on Survey Propagation (SP) equations allows to solve efficiently some combinatorial problems over random graphs.…
Polynomial iterative algorithms for coloring and analyzing random graphs
A. Braunstein, R. Mulet, A. Pagnani +2
We study the graph coloring problem over random graphs of finite average connectivity . Given a number of available colors, we find that graphs with low connectivity admit a…
Constraint Satisfaction by Survey Propagation
A. Braunstein, M. Mezard, M. Weigt +1
Survey Propagation is an algorithm designed for solving typical instances of random constraint satisfiability problems. It has been successfully tested on random 3-SAT and random $…