Dr Andreas Galanis
Tutorial Fellow in Computer Science
Associate Professor in Computer Science
Dr Galanis first studied at the University of Athens, before taking his PhD from the School of Computer Science at Georgia Tech University in Algorithms, Combinatorics, and Optimization. His research focuses on the interplay between approximate counting/sampling problems in computer science and phase transitions in statistical physics. He was recently a postdoctoral researcher in the Oxford Department of Computer Science and joined Hertford in Autumn 2018 as our inaugural Tutorial Fellow in Computer Science.
-
Research interests
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
- The complexity of approximating the matching polynomial in the complex plane.
Preliminary version in ICALP 2019.
I. Bezakova, A. Galanis, L. A. Goldberg, and D. Stefankovic.
arXiv conference - Fast algorithms at low temperatures via Markov chains.
To appear in APPROX/RANDOM 2019.
Z. Chen, A. Galanis, L. A. Goldberg, W. Perkins, J. Stewart, and E. Vigoda.
arXiv - Improved strong spatial mixing for colorings on trees.
To appear in APPROX/RANDOM 2019.
C. Efthymiou, A. Galanis, T. Hayes, D. Stefankovic, and E. Vigoda. - 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.
Electronic Journal of Probability, 23: paper no. 82, 2018.
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 - Approximation via Correlation Decay When Strong Spatial Mixing Fails.
I. Bezakova, A. Galanis, L. A. Goldberg, H. Guo, and D. Stefankovic.
SIAM Journal on Computing, 48(2): 279–349, 2019. Preliminary version in ICALP 2016 (Track A).
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 - 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 - 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 - 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 - Swendsen-Wang Algorithm on the Mean-Field Potts Model.
A. Galanis, D. Stefankovic, and E. Vigoda.
Random Structures & Algorithms, 54(1): 82-147, 2019. Preliminary version in APPROX/RANDOM 2015.
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 - #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
- The complexity of approximating the matching polynomial in the complex plane.