Information theoretic thresholds in a class of probabilistic models on graphs

Speaker: 
Emmanuel Abbe, Princeton University
Date: 
Mar 11 2013 - 4:30pm
Event type: 
PACM Colloquium
Abstract: 

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.