Special Colloquium
Vishesh Jain
MIT
From constraint satisfaction problems to the mean-field approximation, and back
Abstract: The Ising model is one of the most widely studied probabilistic models in statistical physics,
and has found connections to fields as diverse as statistics, theoretical computer science, combinatorics,
machine learning, and economics. A fundamental quantity of interest in the study of Ising models
is the partition function which, despite the simplicity of its definition, is analytically and computationally
intractable. Owing to its myriad applications, there is therefore considerable interest in approximation
schemes for the partition function, of which the mean-field approximation is perhaps the simplest and
most widely used.
In this talk, I will discuss some recent progress in our understanding of the mean-field approximation
for general Ising models. In particular, I will introduce some tools commonly used in the study of
dense constraint satisfaction problems (CSPs), such as correlation rounding, the Frieze-Kannan
weak regularity lemma, and convex programming hierarchies, and discuss how they can be used to
provide strong theoretical and algorithmic results for the mean-field approximation. This connection
between the mean-field approximation and dense CSPs is also profitable in the `reverse direction'
-- the mean-field inapproximability of spin-glasses can be used to show the optimality of correlation
rounding, thereby refuting a conjecture in theoretical computer science.
Based on several joint works with Frederic Koehler (MIT), Elchanan Mossel (MIT), and Andrej Risteski (CMU).
Wednesday January 29, 2020 at 3:00 PM in 636 SEO