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 from the ACO Program at Georgia Tech. I came to Oxford in 2014 as a postdoc, and was a research fellow at the Simons Institute for the Theory of Computing during Spring 2016. I joined the department as a faculty member in 2018.

I am organising the Algorithms and Complexity Theory Seminar.

Fast sampling of satisfying assignments from random k-SAT.
A. Galanis, L. A. Goldberg, H. Guo, and A. Herrera-Poyatos.
arXiv

Metastability of the Potts ferromagnet on random regular graphs.
A. Coja-Oghlan, A. Galanis, L. A. Goldberg, J. B. Ravelomanana, D. Stefankovic, and E. Vigoda.
Preliminary version in ICALP 2022.
arXiv conference

Fast sampling via spectral independence beyond bounded-degree graphs.
I. Bezakova, A. Galanis, L. A. Goldberg, and D. Stefankovic.
Preliminary version in ICALP 2022.
arXiv conference

Approximating observables is as hard as counting.
A. Galanis, D. Stefankovic, and E. Vigoda.
Preliminary version in ICALP 2022.
arXiv conference

Inapproximability of counting hypergraph colourings.
A. Galanis, H. Guo, and J. Wang.
To appear in ACM Transactions on Computation Theory, 2022.
arXiv

Fast mixing via polymers for random graphs with unbounded degree.
A. Galanis, L. A. Goldberg, and J. Stewart.
Information and Computation, Volume 285, 2022. Preliminary version in APPROX/RANDOM 2021.
arXiv conference journal

The complexity of approximating the complex-valued Ising model on bounded degree graphs.
A. Galanis, L. A. Goldberg, and A. Herrera-Poyatos.
To appear in SIAM Journal on Discrete Mathematics, 2022.
arXiv

Sampling colorings and independent sets of random regular bipartite graphs in the non-uniqueness region.
Z. Chen, A. Galanis, D. Stefankovic, and E. Vigoda.
Preliminary version in SODA 2022.
arXiv conference

Lee-Yang zeros and the complexity of the ferromagnetic Ising Model on bounded-degree graphs.
P. Buys, A. Galanis, V. Patel, and G. Regts.
Forum of Mathematics, Sigma, Volume 10, 2022. Preliminary version in SODA 2021.
arXiv conference journal

Rapid mixing for colorings via spectral independence.
Z. Chen, A. Galanis, D. Stefankovic, and E. Vigoda.
Preliminary version in SODA 2021.
arXiv conference

The complexity of approximating averages on bounded-degree graphs.
A. Galanis, D. Stefankovic, and E. Vigoda.
Preliminary version in FOCS 2020.
arXiv conference

Counting solutions to random CNF formulas.
A. Galanis, L. A. Goldberg, H. Guo, and K. Yang.
SIAM Journal on Computing, 50(6): 1701-1738, 2021. Preliminary version in ICALP 2020.
arXiv conference journal

The complexity of approximating the complex-valued Potts model.
A. Galanis, L. A. Goldberg, and A. Herrera-Poyatos.
Computational Complexity, 31: Article No. 2, 2022. Preliminary version in MFCS 2020.
arXiv conference journal

Fast algorithms for general spin systems on bipartite expanders.
A. Galanis, L. A. Goldberg, and J. Stewart.
ACM Transactions on Computation Theory, 13(4): Article No. 25, 2021. Preliminary version in MFCS 2020.
arXiv conference journal

Inapproximability of the independent set polynomial in the complex plane.
I. Bezakova, A. Galanis, L. A. Goldberg, and D. Stefankovic.
SIAM Journal on Computing, 49(5):STOC18-395-STOC18-448, 2020. Preliminary version in STOC 2018.
Invited to STOC 2018 special issue.
arXiv conference journal

Fast algorithms at low temperatures via Markov chains.
Z. Chen, A. Galanis, L. A. Goldberg, W. Perkins, J. Stewart, and E. Vigoda.
Random Structures & Algorithms, 58(2): 294– 321, 2021. Preliminary version in APPROX/RANDOM 2019.
arXiv conference journal

The complexity of approximating the matching polynomial in the complex plane.
I. Bezakova, A. Galanis, L. A. Goldberg, and D. Stefankovic.
ACM Transactions on Computation Theory, 13(2): Article No. 13, 2021. Preliminary version in ICALP 2019.
arXiv conference journal

Sampling in uniqueness from the Potts and random-cluster models on random regular graphs.
A. Blanca, A. Galanis, L. A. Goldberg, D. Stefankovic, E. Vigoda, and K. Yang.
SIAM Journal on Discrete Mathematics, 34(1): 742–793, 2019. Preliminary version in APPROX/RANDOM 2018.
arXiv conference journal

Improved strong spatial mixing for colorings on trees.
C. Efthymiou, A. Galanis, T. Hayes, D. Stefankovic, and E. Vigoda.
Preliminary version in APPROX/RANDOM 2019.
arXiv conference

Uniqueness for the 3-state antiferromagnetic Potts model on the tree.
A. Galanis, L. A. Goldberg, and K. Yang.
Electronic Journal of Probability, 23: paper no. 82, 2018.
arXiv journal

Random walks on small world networks.
M. E. Dyer, A. Galanis, L. A. Goldberg, M. Jerrum, and E. Vigoda.
ACM Transactions on Algorithms, 16(3): Article No. 37, 2020.
arXiv journal

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.
Journal of Computer and System Sciences, 115: 187-213, 2021. Preliminary version in ICALP 2017 (Track A).
arXiv conference journal

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