2.5k citations · 10k across the 171 of their papers we have counts for
15 papers · 1 filter
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…
On the deletion channel with small deletion probability
Yashodhan Kanoria, Andrea Montanari
The deletion channel is the simplest point-to-point communication channel that models lack of synchronization. Despite significant effort, little is known about its capacity, and e…
Tight Thresholds for Cuckoo Hashing via XORSAT
Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher +3
We settle the question of tight thresholds for offline cuckoo hashing. The problem can be stated as follows: we have n keys to be hashed into m buckets each capable of holding a si…
Message Passing Algorithms for Compressed Sensing: II. Analysis and Validation
David L. Donoho, Arian Maleki, Andrea Montanari
In a recent paper, the authors proposed a new class of low-complexity iterative thresholding algorithms for reconstructing sparse signals from a small set of linear measurements \c…
Message Passing Algorithms for Compressed Sensing: I. Motivation and Construction
David L. Donoho, Arian Maleki, Andrea Montanari
In a recent paper, the authors proposed a new class of low-complexity iterative thresholding algorithms for reconstructing sparse signals from a small set of linear measurements \c…
Low-rank Matrix Completion with Noisy Observations: a Quantitative Comparison
Raghunandan H. Keshavan, Andrea Montanari, Sewoong Oh
We consider a problem of significant practical importance, namely, the reconstruction of a low-rank data matrix from a small subset of its entries. This problem appears in many are…
A Natural Dynamics for Bargaining on Exchange Networks
Yashodhan Kanoria, Mohsen Bayati, Christian Borgs +2
Bargaining networks model the behavior of a set of players that need to reach pairwise agreements for making profits. Nash bargaining solutions are special outcomes of such games t…
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…
Message Passing Algorithms for Compressed Sensing
David L. Donoho, Arian Maleki, Andrea Montanari
Compressed sensing aims to undersample certain high-dimensional signals, yet accurately reconstruct them by exploiting signal characteristics. Accurate reconstruction is possible w…
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…
Matrix Completion from Noisy Entries
Raghunandan H. Keshavan, Andrea Montanari, Sewoong Oh
Given a matrix M of low-rank, we consider the problem of reconstructing it from noisy observations of a small, random subset of its entries. The problem arises in a variety of appl…
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…