124 citations · 239 across the 28 of their papers we have counts for
5 papers · 1 filter
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…
The complexity of approximating the complex-valued Potts model
Andreas Galanis, Leslie Ann Goldberg, Andrés Herrera-Poyatos
We study the complexity of approximating the partition function of the -state Potts model and the closely related Tutte polynomial for complex values of the underlying parameter…
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…
The complexity of approximating averages on bounded-degree graphs
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
We prove that, unless P=NP, there is no polynomial-time algorithm to approximate within some multiplicative constant the average size of an independent set in graphs of maximum deg…