Andreas Galanis


Department of Computer Science
University of Oxford
Wolfson Bldg, Parks Rd
Oxford, OX1 3QD UK

agalanis@cs.ox.ac.uk
galanis.an@gmail.com

www.cs.ox.ac.uk/people/andreas.galanis

Andreas Galanis



I am a postdoctoral researcher in the Department of Computer Science at the University of Oxford, working with Leslie Ann Goldberg. This year, I am teaching the courses Probability and Algorithms at Hertford College.

During Spring 2016, I was a Research Fellow at the Simons Institute for the Theory of Computing in the program "Counting Complexity and Phase Transitions". I received my Phd in Algorithms, Combinatorics, and Optimization from the School of Computer Science at Georgia Tech, advised by Eric Vigoda. At Georgia Tech, I also obtained an MS in mathematics. Prior to that, I got an MS in Logic, Algorithms & Computation at the University of Athens, and a diploma in electrical and computer engineering at the National Technical University of Athens.

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.


Publications & Preprints


Inapproximability of the independent set polynomial in the complex plane.
I. Bezakova, A. Galanis, L. A. Goldberg, and D. Stefankovic.
arXiv

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

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