2.5k citations · 10k across the 171 of their papers we have counts for
23 papers · 1 filter
Free energy of Ising models under a spectral condition
Andrea Montanari, Michael Ren
A sequence of sparse weighted graphs indexed by the number of vertices is said to be left-convergent if all (suitably weighted) subgraph counts converge to a lim…
Shattering in Pure Spherical Spin Glasses
Ahmed El Alaoui, Andrea Montanari, Mark Sellke
We prove the existence of a shattered phase within the replica-symmetric phase of the pure spherical -spin models for sufficiently large. In this phase, we construct a decom…
Solving systems of Random Equations via First and Second-Order Optimization Algorithms
Andrea Montanari, Eliran Subag
We revisit the problem of solving random equations in real variables, when the equations are independent realizations of a Gaussian process in dimensions. A special cas…
Optimization of random high-dimensional functions: Structure and algorithms
Antonio Auffinger, Andrea Montanari, Eliran Subag
Replica symmetry breaking postulates that near optima of spin glass Hamiltonians have an ultrametric structure. Namely, near optima can be associated to leaves of a tree, and the E…
Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization
Ahmed El Alaoui, Andrea Montanari, Mark Sellke
We consider the Sherrington-Kirkpatrick model of spin glasses at high-temperature and no external field, and study the problem of sampling from the Gibbs distribution in polyno…
The high-dimensional asymptotics of first order methods with random data
Michael Celentano, Chen Cheng, Andrea Montanari
We study a class of deterministic flows in , parametrized by a random matrix with i.i.d. centered subgaussian…
Local algorithms for Maximum Cut and Minimum Bisection on locally treelike regular graphs of large degree
Ahmed El Alaoui, Andrea Montanari, Mark Sellke
Given a graph of degree over vertices, we consider the problem of computing a near maximum cut or a near minimum bisection in polynomial time. For graphs of girth ,…
Optimization of Mean-field Spin Glasses
Ahmed El Alaoui, Andrea Montanari, Mark Sellke
Mean-field spin glasses are families of random energy functions (Hamiltonians) on high-dimensional product spaces. In this paper we consider the case of Ising mixed -spin models…
On the computational tractability of statistical estimation on amenable graphs
Ahmed El Alaoui, Andrea Montanari
We consider the problem of estimating a vector of discrete variables , based on noisy observations of the pairs on the edges of a graph $G=([…
Optimization of the Sherrington-Kirkpatrick Hamiltonian
Andrea Montanari
Let be a symmetric random matrix with independent and identically distributed Gaussian entries above the diagonal. We consider the probl…
TAP free energy, spin glasses, and variational inference
Zhou Fan, Song Mei, Andrea Montanari
We consider the Sherrington-Kirkpatrick model of spin glasses with ferromagnetically biased couplings. For a specific choice of the couplings mean, the resulting Gibbs measure is e…
The Spectral Norm of Random Inner-Product Kernel Matrices
Zhou Fan, Andrea Montanari
We study an "inner-product kernel" random matrix model, whose empirical spectral distribution was shown by Xiuyuan Cheng and Amit Singer to converge to a deterministic measure in t…
Conditional Random Fields, Planted Constraint Satisfaction, and Entropy Concentration
Emmanuel Abbe, Andrea Montanari
This paper studies a class of probabilistic models on graphs, where edge variables depend on incident node variables through a fixed probability kernel. The class includes planted…
Finding Hidden Cliques of Size \sqrt{N/e} in Nearly Linear Time
Yash Deshpande, Andrea Montanari
Consider an Erdös-Renyi random graph in which each edge is present independently with probability 1/2, except for a subset $\sC_N$ of the vertices that form a clique (a completely…
State Evolution for General Approximate Message Passing Algorithms, with Applications to Spatial Coupling
Adel Javanmard, Andrea Montanari
We consider a class of approximated message passing (AMP) algorithms and characterize their high-dimensional behavior in terms of a suitable state evolution recursion. Our proof ap…
Universality in polytope phase transitions and message passing algorithms
Mohsen Bayati, Marc Lelarge, Andrea Montanari
We consider a class of nonlinear mappings in indexed by symmetric random matrices with independent entries. Within sp…
Factor models on locally tree-like graphs
Amir Dembo, Andrea Montanari, Nike Sun
We consider homogeneous factor models on uniformly sparse graph sequences converging locally to a (unimodular) random tree , and study the existence of the free energy density $…
The weak limit of Ising models on locally tree-like graphs
Andrea Montanari, Elchanan Mossel, Allan Sly
We consider the Ising model with inverse temperature beta and without external field on sequences of graphs G_n which converge locally to the k-regular tree. We show that for such…
Gibbs Measures and Phase Transitions on Sparse Random Graphs
Amir Dembo, Andrea Montanari
Many problems of interest in computer science and information theory can be phrased in terms of a probability distribution over discrete variables associated to the vertices of a l…
Majority dynamics on trees and the dynamic cavity method
Yashodhan Kanoria, Andrea Montanari
A voter sits on each vertex of an infinite tree of degree , and has to decide between two alternative opinions. At each time step, each voter switches to the opinion of the majo…
Ising models on locally tree-like graphs
Amir Dembo, Andrea Montanari
We consider ferromagnetic Ising models on graphs that converge locally to trees. Examples include random regular graphs with bounded degree and uniformly random graphs with bounded…
Reconstruction for models on random graphs
Antoine Gerschenfeld, Andrea Montanari
Consider a collection of random variables attached to the vertices of a graph. The reconstruction problem requires to estimate one of them given `far away' observations. Several th…
Finite size scaling for the core of large random hypergraphs
Amir Dembo, Andrea Montanari
The (two) core of a hypergraph is the maximal collection of hyperedges within which no vertex appears only once. It is of importance in tasks such as efficiently solving a large li…