Showing cs.DSShow all
3 papers · 1 filter
cs.DS2021
Fast mixing via polymers for random graphs with unbounded degree
Andreas Galanis, Leslie Ann Goldberg, James Stewart
The polymer model framework is a classical tool from statistical mechanics that has recently been used to obtain approximation algorithms for spin systems on classes of bounded-deg…
cs.DS2020
Fast algorithms for general spin systems on bipartite expanders
Andreas Galanis, Leslie Ann Goldberg, James Stewart
A spin system is a framework in which the vertices of a graph are assigned spins from a finite set. The interactions between neighbouring spins give rise to weights, so a spin assi…
cs.DS2019
Fast algorithms at low temperatures via Markov chains
Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg +3
We define a discrete-time Markov chain for abstract polymer models and show that under sufficient decay of the polymer weights, this chain mixes rapidly. We apply this Markov chain…