Information theoretic thresholds in a class of probabilistic models on graphs

Monday, March 11, 2013 -
4:30pm to 5:30pm
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.
Speaker: 
Emmanuel Abbe
Princeton University
Event Location: 
Fine Hall 214