2.5k citations · 10k across the 171 of their papers we have counts for
9 papers · 1 filter
Coding for Network Coding
Andrea Montanari, Ruediger Urbanke
We consider communication over a noisy network under randomized linear network coding. Possible error mechanism include node- or link- failures, Byzantine behavior of nodes, or an…
Detailed Network Measurements Using Sparse Graph Counters: The Theory
Yi Lu, Andrea Montanari, Balaji Prabhakar
Measuring network flow sizes is important for tasks like accounting/billing, network forensics and security. Per-flow accounting is considered hard because it requires that many co…
TP Decoding
Yi Lu, Cyril Measson, Andrea Montanari
`Tree pruning' (TP) is an algorithm for probabilistic inference on binary Markov random fields. It has been recently derived by Dror Weitz and used to construct the first fully pol…
Estimating Random Variables from Random Sparse Observations
Andrea Montanari
Let X_1,...., X_n be a collection of iid discrete random variables, and Y_1,..., Y_m a set of noisy observations of such variables. Assume each observation Y_a to be a random funct…
Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian
Message passing algorithms have proved surprisingly successful in solving hard constraint satisfaction problems on sparse random graphs. In such applications, variables are fixed s…
A simple one dimensional glassy Kac model
Andrea Montanari, Antoine Sinton
We define a new family of random spin models with one-dimensional structure, finite-range multi-spin interactions, and bounded average degree (number of interactions in which each…
Modern Coding Theory: The Statistical Mechanics and Computer Science Point of View
Andrea Montanari, Rudiger Urbanke
These are the notes for a set of lectures delivered by the two authors at the Les Houches Summer School on `Complex Systems' in July 2006. They provide an introduction to the basic…
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…