Stats Dept. presents"From CSPs to the mean-field approximation, and back"

From CSPs to the mean-field approximation, and back
Tuesday, January 7, 2020 - 4:30pm
Sloan Mathematics Center, Room 380C
Vishesh Jain (MIT)
Abstract / Description: 

The mean-field approximation is a canonical variational technique used in the analysis and inference of Ising models. Owing to its popularity, much work in recent years has gone into understanding its performance for general Ising models. In this talk, I will introduce some tools commonly used in the study of dense constraint satisfaction problems (CSPs), such as correlation rounding and the Frieze–Kannan weak regularity lemma, and discuss how they can be used to provide sharp estimates on the quality of the mean-field approximation in a very simple manner. This connection between the mean-field approximation and dense CSPs is also profitable in the “reverse direction”: in particular, I will discuss how the mean-field inapproximability of spin-glasses can be used to show the optimality of correlation rounding, thereby refuting a conjecture due to Allen, O’Donnell, and Zhou. This is based on joint works with Frederic Koehler (MIT), Elchanan Mossel (MIT), and Andrej Risteski (CMU).


The Statistics Seminars for Winter Quarter will be held in Room 380C of Sloan Mathematics Center in the Main Quad at 4:30pm on Tuesdays. Refreshments are served at 4pm in the Lounge on the first floor of Sequoia Hall.