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 points. We prove that there is at most one non-trivial fixed point for Ising models with zero or certain random external fields. Previously this was only known for sufficiently ``low-temperature'' models.
Our result simultaneously closes the following 6 conjectures in the literature: 1) independence of robust reconstruction accuracy to leaf noise in broadcasting on trees (Mossel-Neeman-Sly'16); 2) uselessness of global information for a labeled 2-community stochastic block model, or 2-SBM (Kanade-Mossel-Schramm'16); 3) optimality of local algorithms for 2-SBM under noisy side information (Mossel-Xu'16); 4) uniqueness of BP fixed point in broadcasting on trees in the Gaussian (large degree) limit (ibid); 5) boundary irrelevance in broadcasting on trees (Abbe-Cornacchia-Gu-Polyanskiy'21); 6) characterization of entropy (and mutual information) of community labels given the graph in 2-SBM (ibid).
This is a joint work with Yury Polyanskiy.
Paper link: https://arxiv.org/abs/2211.15242
Probability and Combinatorics
Tuesday, April 11, 2023 - 3:30pm
Qian Yu
Princeton University
Other Events on This Day
-
Cutoff profile of the colored ASEP: GOE Tracy-Widom
Probability and Combinatorics
4:30pm
-
Wiggling and paddling: exploring Tomopteris swimming performance
MathBio Seminar
4:00pm