1 citations · 1 across the 1 of their papers we have counts for
8 papers
Rapid Mixing for Colorings via Spectral Independence
Zongchen Chen, Andreas Galanis, Daniel Štefankovič +1
The spectral independence approach of Anari et al. (2020) utilized recent results on high-dimensional expanders of Alev and Lau (2020) and established rapid mixing of the Glauber d…
Lee-Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
Pjotr Buys, Andreas Galanis, Viresh Patel +1
We study the computational complexity of approximating the partition function of the ferromagnetic Ising model with the external field parameter on the unit circle in the compl…
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…
Improved Strong Spatial Mixing for Colorings on Trees
Charilaos Efthymiou, Andreas Galanis, Thomas P. Hayes +2
Strong spatial mixing (SSM) is a form of correlation decay that has played an essential role in the design of approximate counting algorithms for spin systems. A notable example is…
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…
The complexity of approximating the matching polynomial in the complex plane
Ivona Bezakova, Andreas Galanis, Leslie Ann Goldberg +1
We study the problem of approximating the value of the matching polynomial on graphs with edge parameter , where takes arbitrary values in the complex plane. When is a p…