We introduce a class of probabilistic models on graphs motivated by coding and combinatorial optimization problems (e.g., LDPC codes, k-SAT, clustering). We show that for a large class of models, the conditional entropy between the information at the nodes and at the edges concentrates around a determnistic threshold. Joint work with A. Montanari.
Information theoretic thresholds in a class of probabilistic models on graphs
Emmanuel Abbe, Princeton University
Mar 11 2013 - 4:30pm