SILO: Variational Inference, MCMC, and Dense SoftMax-Cut

A famous result in approximation algorithms is that the max-cut problem can be approximated up to (1 + \epsilon) error in polynomial time on dense graphs. Motivated by connections to markov chains, variational inference, and statistical physics, we show that this result can be recovered from a stronger fact: a corresponding “softmax” distribution over all cuts can be sampled in polynomial time. This is a special case of a more general result which has applications to other sampling problems, e.g. related to Bayesian statistics, spin glasses, and expander graphs. Based on a joint work with Holden Lee and Andrej Risteski.

Frederic is an assistant professor at the University of Chicago in the Department of Statistics and the Data Science Institute. Previously, he was a Rajeev Motwani fellow at Stanford computer science, and before that was at the Simons Institute and at MIT. His research interests include high-dimensional statistics, sampling algorithms, generative modeling, and the interaction between computational and statistical complexity.