2.5k citations · 10k across the 171 of their papers we have counts for
4 papers · 1 filter
Learning Low Rank Matrices from O(n) Entries
Raghunandan H. Keshavan, Andrea Montanari, Sewoong Oh
How many random entries of an n by m, rank r matrix are necessary to reconstruct the matrix within an accuracy d? We address this question in the case of a random matrix with bound…
Generating Random Networks Without Short Cycles
Mohsen Bayati, Andrea Montanari, Amin Saberi
Random graph generation is an important tool for studying large complex networks. Despite abundance of random graph models, constructing models with application-driven constraints…
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…
Clusters of solutions and replica symmetry breaking in random k-satisfiability
Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian
We study the set of solutions of random k-satisfiability formulae through the cavity method. It is known that, for an interval of the clause-to-variables ratio, this decomposes int…