Andreas Galanis


Department of Computer Science, University of Oxford
Associate Professor of Algorithms & Complexity Theory
Tutorial Fellow at Hertford College

agalanis@cs.ox.ac.uk
galanis.an@gmail.com
Room 312 (department), OB3/5 (college)
www.cs.ox.ac.uk/people/andreas.galanis

Andreas Galanis


Research: My main research focus is the interplay between approximate counting/sampling problems in computer science and phase transitions in statistical physics. More generally, I am interested in the analysis of stochastic processes motivated by applications in computer science and related areas.

Short CV: I received my Phd in Algorithms, Combinatorics and Optimization from the School of Computer Science at Georgia Tech. I came to Oxford in 2014 as a postdoc in the MCC project, and was a research fellow at the Simons Institute during spring 2016. I joined the Department of Computer Science as a faculty member in 2018.


Publications & Preprints

Inapproximability of the independent set polynomial in the complex plane.
Submitted. Preliminary version in STOC 2018.
I. Bezakova, A. Galanis, L. A. Goldberg, and D. Stefankovic.
arXiv conference

Sampling in uniqueness from the Potts and random-cluster models on random regular graphs.
Submitted. Preliminary version in APPROX/RANDOM 2018.
A. Blanca, A. Galanis, L. A. Goldberg, D. Stefankovic, E. Vigoda, and K. Yang.
arXiv conference

Uniqueness for the 3-state antiferromagnetic Potts model on the tree.
A. Galanis, L. A. Goldberg, and K. Yang.
arXiv journal

Random Walks on Small World Networks.
M. E. Dyer, A. Galanis, L. A. Goldberg, M. Jerrum, and E. Vigoda.
arXiv

Inapproximability of the independent set polynomial below the Shearer threshold.
A. Galanis, L. A. Goldberg, and D. Stefankovic.
Submitted. Preliminary version in ICALP 2017 (Track A).
arXiv conference

Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems.
A. Galanis, L. A. Goldberg, and K. Yang.
Submitted. Preliminary version in ICALP 2017 (Track A).
arXiv conference

Rapid Mixing Swendsen-Wang Sampler for Stochastic Partitioned Attractive Models.
S. Park, Y. Jang, A. Galanis, J. Shin, D. Stefankovic, and E. Vigoda.
Preliminary version in AISTATS 2017.
arXiv conference

Swendsen-Wang Algorithm on the Mean-Field Potts Model.
A. Galanis, D. Stefankovic, and E. Vigoda.
To appear in Random Structures & Algorithms. Preliminary version in APPROX/RANDOM 2015.
arXiv conference journal

Amplifiers for the Moran Process.
A. Galanis, A. Göbel, L. A. Goldberg, J. Lapinskas, and D. Richerby.
Journal of the ACM, 64(1): Article No. 5, 2017. Preliminary version in ICALP 2016 (Track A) (Best Paper Award).
arXiv conference journal

Approximately Counting H-Colorings is #BIS-Hard.
A. Galanis, L. A. Goldberg, and M. Jerrum.
SIAM Journal on Computing, 45(3): 680–711, 2016. Preliminary version in ICALP 2015 (Track A)
arXiv conference journal

Inapproximability for Antiferromagnetic Spin Systems in the Tree Non-Uniqueness Region.
A. Galanis, D. Stefankovic, and E. Vigoda.
Journal of the ACM, 62(6): Article No. 50, 2015. Preliminary version in STOC 2014.
arXiv conference journal

Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results.
A. Galanis, D. Stefankovic, E. Vigoda, and L. Yang.
SIAM Journal on Computing, 45(6): 2004–2065, 2016. Preliminary version in APPROX/RANDOM 2014.
arXiv conference journal

A Complexity Trichotomy for Approximately Counting List H-Colourings.
A. Galanis, L. A. Goldberg, and M. Jerrum.
ACM Transactions on Computation Theory, 9(2): Article No.9, 2017. Preliminary version in ICALP 2016 (Track A).
arXiv conference journal

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs.
A. Galanis and L. A. Goldberg.
Information and Computation, 251: 36–66, 2016. Preliminary version in SODA 2016.
arXiv conference journal

Approximation via Correlation Decay When Strong Spatial Mixing Fails.
I. Bezakova, A. Galanis, L. A. Goldberg, H. Guo, and D. Stefankovic.
Submitted. Preliminary version in ICALP 2016 (Track A).
arXiv conference

#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region.
J.-Y. Cai, A. Galanis, L. A. Goldberg, H. Guo, M. Jerrum, D. Stefankovic, and E. Vigoda.
Journal of Computer and System Sciences, 82(5): 690–711, 2016. Preliminary version in APPROX/RANDOM 2014.
arXiv conference journal

Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models.
A. Galanis, D. Stefankovic, and Eric Vigoda.
Combinatorics, Probability & Computing, 25(4): 500–559, 2016.
arXiv journal

Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model.
A. Galanis, Q. Ge, D. Stefankovic, E. Vigoda, and L. Yang.
Random Structures & Algorithms, 45(1): 78–110, 2014. Preliminary version in APPROX/RANDOM 2011.
arXiv conference journal