SILO: Variational Inference, MCMC, and Dense SoftMax-Cut
Abstract: 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: …