Name
Abstract | ||
|---|---|---|
Vindicating a sophisticated but non-rigorous physics approach called the cavity method, we establish a formula for the mutual information in statistical inference problems induced by random graphs. This general result implies the conjecture on the information-theoretic threshold in the disassortative stochastic block model [Decelle et al.: Phys. Rev. E (2011)] and allows us to pinpoint the exact condensation phase transition in random constraint satisfaction problems such as random graph coloring, thereby proving a conjecture from [Krzakala et al.: PNAS (2007)]. As a further application we establish the formula for the mutual information in Low-Density Generator Matrix codes as conjectured in [Montanari: IEEE Transactions on Information Theory (2005)]. The proofs provide a conceptual underpinning of the replica symmetric variant of the cavity method, and we expect that the approach will find many future applications. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1145/3055399.3055420 | STOC |
Keywords | DocType | Volume |
Cavity method,Belief Propagation,Stochastic block model,Random graph coloring,Information theoretic thresholds | Conference | abs/1611.00814 |
ISSN | Citations | PageRank |
Advances in Mathematics Volume 333, 31 July 2018, Pages 694-795 | 0 | 0.34 |
References | Authors | |
8 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amin Coja-Oghlan | 1 | 543 | 47.25 |
| Florent Krzakala | 2 | 977 | 67.30 |
| Will Perkins | 3 | 51 | 13.01 |
| Lenka Zdeborová | 4 | 1190 | 78.62 |