Information theoretic thresholds in a class of probabilistic models on graphs

Information theoretic thresholds in a class of probabilistic models on graphs

-
Emmanuel Abbe, Princeton University
Fine Hall 214

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.