#  Seminar: Yury Polyanskiy (MIT): "Uniqueness of BP fixed point for Ising models" 

 



####  calendar\_today Date and Time 

 **February 22, 2022** 

 09:30AM - 09:30AM EST 

####  pin\_drop Location 

 **Zoom: https://harvard.zoom.us/j/779283357?pwd=MitXVm1pYUlJVzZqT3lwV2pCT1ZUQT09**  



 

 



 

 **![Yury Polyanskiy](/sites/g/files/omnuum6611/files/styles/hwp_1_1__360x360_scale/public/mathpicture/files/yury_polyanskiy.jpg?itok=pqs1YeSV) 

 

  
Speaker:** Yury Polyanskiy (MIT)  
**Title:** Uniqueness of BP fixed point for Ising models  
**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 distributional recursions and its fixed point (also known as Bethe fixed point, cavity equation etc). In this work we prove there is at most one non-trivial fixed point for Ising models with zero and certain random external fields. As a concrete example, consider a sample A of Ising model on a rooted tree (regular, Galton-Watson, etc). Let B be a noisy version of A obtained by independently perturbing each spin as follows: Bv equals to Av with some small probability δ and otherwise taken to be a uniform +-1 (alternatively, 0). We show that the distribution of the root spin Aρ conditioned on values Bv of all vertices v at a large distance from the root is independent of δ and coincides with δ=0. Previously this was only known for sufficiently ``low-temperature'' models. Our proof consists of constructing a metric under which the BP operator is a contraction (albeit non-multiplicative). I hope to convince you our proof is technically rather simple.

 This simultaneously closes the following 5 conjectures in the literature: uselessness of global information for a labeled 2-community stochastic block model, or 2-SBM (Kanade-Mossel-Schramm'2014); optimality of local algorithms for 2-SBM under noisy side information (Mossel-Xu'2015); independence of robust reconstruction accuracy to leaf noise in broadcasting on trees (Mossel-Neeman-Sly'2016); boundary irrelevance in BOT (Abbe-Cornacchia-Gu-P.'2021); characterization of entropy of community labels given the graph in 2-SBM (ibid).  
Joint work with Qian Yu (Princeton).



 

 

---

 Attachments- [  picture\_as\_pdf  2022-02-22\_polyanskiy\_seminar.pdf ](/sites/g/files/omnuum6611/files/mathpicture/files/2022-02-22_polyanskiy_seminar.pdf)
 
---

 



 

 

 Share on:- [     Facebook ](#)
- [     Twitter ](#)
- [     Linkedin ](#)
 


 Save: [ Add to calendar calendar\_today ](https://mathpicture.fas.harvard.edu/node/1624029/event-feed.ics)  Copy link link