553 citations · 1.3k across the 25 of their papers we have counts for
5 papers · 1 filter
Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
Florent Krzakala, Andrea Montanari, Federico Ricci-Tersenghi +2
An instance of a random constraint satisfaction problem defines a random subset S (the set of solutions) of a large product space (the set of assignments). We consider two prototyp…
Counting good truth assignments of random k-SAT formulae
Andrea Montanari, Devavrat Shah
We present a deterministic approximation algorithm to compute logarithm of the number of `good' truth assignments for a random k-satisfiability (k-SAT) formula in polynomial time (…
How to Find Good Finite-Length Codes: From Art Towards Science
Abdelaziz Amraoui, Andrea Montanari, Ruediger Urbanke
We explain how to optimize finite-length LDPC codes for transmission over the binary erasure channel. Our approach relies on an analytic approximation of the erasure probability. T…
Rigorous Inequalities between Length and Time Scales in Glassy Systems
Andrea Montanari, Guilhem Semerjian
Glassy systems are characterized by an extremely sluggish dynamics without any simple sign of long range order. It is a debated question whether a correct description of such pheno…
Analysis of Belief Propagation for Non-Linear Problems: The Example of CDMA (or: How to Prove Tanaka's Formula)
Andrea Montanari, David Tse
We consider the CDMA (code-division multiple-access) multi-user detection problem for binary signals and additive white gaussian noise. We propose a spreading sequences scheme base…