Skip to main content
Foundations of Information, Networks, and Decision Systems

FIND Seminar

The FIND Seminar is a bi-weekly seminar series that hosts cutting-edge research talks on topics related to the broad themes of Foundations of Information, Networks and Decision Systems. Talks are about 50 minutes long with time for questions and discussion.

Location: Phillips Hall 233 and Zoom
Time: 4:10PM ET, bi-weekly on (alternating) Thursdays, starting 10th Feb 2022

Delivery format: All talks will have a live audience in Phillips Hall 223. Until circumstances allow otherwise, external speakers will give the talk remotely via Zoom (broadcasted in PH223). Remote audience is also welcome, but in-person participation is encouraged.

Mailing list: To subscribe to the FIND seminar mailing list, email find-seminar-l-request@cornell.edu, with “join” in the subject line and a blank email body. All talks info and reminders will be sent via the mailing list.

Upcoming Talk
Title: Uniqueness of belief propagation fixed point
Speaker:
Yury Polyanskiy
Date and Time: 
12/01/2022 4:10PM ET
Location:
Phillips Hall 223 and Zoom

Abstract:

In the study of Ising models on large locally tree-like graphs, in both rigorous and non-rigorous methods one is often led to understanding the so-called belief propagation (BP) distributional recursion and its fixed point (also known as Bethe fixed point, cavity equation, 1RSB). In this work we prove there is at most one non-trivial fixed point for Ising models for both zero and certain random external fields. This long sought-after result simultaneously resolves 6 conjectures formulated over the last 10+ years in the literature on stochastic block models and Ising models. Interestingly, our proof is based on information-theoretic ideas of channel comparison and is rather simple. 

A machine learning application is in the area of community detection in which n vertices are assigned equiprobable hidden binary labels and the adjacent vertices are connected with probability a/n or b/n depending on whether they have the same label or not. The goal is to reconstruct the latent community structure based on observation of the graph only. BP-uniqueness implies that a simple efficient algorithm—BP initialized by the sign of the second eigenvector—achieves optimal recovery rate, exactly matching performance of the exponential-time maximum likelihood estimator.

Joint work with Qian Yu (Princeton).

 

Schedule for Fall 2022: 

A list of previous talks can be found here.

Skip to toolbar