124 citations · 239 across the 28 of their papers we have counts for
5 papers · 1 filter
Amplifiers for the Moran Process
Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg +2
The Moran process, as studied by Lieberman, Hauert and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlyin…
Approximation via Correlation Decay when Strong Spatial Mixing Fails
Ivona Bezakova, Andreas Galanis, Leslie Ann Goldberg +2
Approximate counting via correlation decay is the core algorithmic technique used in the sharp delineation of the computational phase transition that arises in the approximation of…
The complexity of approximately counting in 2-spin systems on -uniform bounded-degree hypergraphs
Andreas Galanis, Leslie Ann Goldberg
One of the most important recent developments in the complexity of approximate counting is the classification of the complexity of approximating the partition functions of antiferr…
Swendsen-Wang Algorithm on the Mean-Field Potts Model
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
We study the -state ferromagnetic Potts model on the -vertex complete graph known as the mean-field (Curie-Weiss) model. We analyze the Swendsen-Wang algorithm which is a Mar…
Approximately Counting H-Colourings is #BIS-Hard
Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum
We consider the problem of counting H-colourings from an input graph G to a target graph H. We show that if H is any fixed graph without trivial components, then the problem is as…