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

**12/01/2022 4:10PM ET**

**Date and Time:****Phillips Hall 223 and Zoom**

**Location:****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: **

Date | Speaker | Title |

09/08/2022 | Mark Wilde | Inevitability of Knowing Less Than Nothing |

09/22/2022 | FIND Community | FIND Graduate Day |

09/29/2022 | Haim Permuter | Data-Driven Approach for Estimating Information Measures |

10/06/2022 | Michael Bailey | The Role of Social Networks in Economic Mobility |

10/20/2022 | Angelia Nedic | Penalty Methods for Large-Scale Constrained Optimization Problems |

11/17/2022 | Youssef Mroueh | Learning with Stochastic Orders |

12/01/2022 | Yury Polyanskiy | Uniqueness of belief propagation fixed point |

A list of previous talks can be found here.