553 citations · 1.2k across the 21 of their papers we have counts for
5 papers · 1 filter
Which graphical models are difficult to learn?
Jose Bento, Andrea Montanari
We consider the problem of learning the structure of Ising models (pairwise binary Markov random fields) from i.i.d. samples. While several methods have been proposed to accomplish…
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…
Reconstruction and Clustering in Random Constraint Satisfaction Problems
Andrea Montanari, Ricardo Restrepo, Prasad Tetali
Random instances of Constraint Satisfaction Problems (CSP's) appear to be hard for all known algorithms, when the number of constraints per variable lies in a certain interval. Con…
An Implementable Scheme for Universal Lossy Compression of Discrete Markov Sources
Shirin Jalali, Andrea Montanari, Tsachy Weissman
We present a new lossy compressor for discrete sources. For coding a source sequence , the encoder starts by assigning a certain cost to each reconstruction sequence. It then…
Matrix Completion from a Few Entries
Raghunandan H. Keshavan, Andrea Montanari, Sewoong Oh
Let M be a random (alpha n) x n matrix of rank r<<n, and assume that a uniformly random subset E of its entries is observed. We describe an efficient algorithm that reconstructs M…