• Study here
    • Study here
    • Undergraduates
    • Graduates
    • Visiting students
    • Outreach with schools and colleges
  • Living here
    • Living here
    • Where you will live
    • Eating here
    • Library & resources
    • Chapel & Faith
    • Do what you love
    • Help is on hand
  • Our people
  • News, events and more
    • News, events and more
    • Our vision for 2030
    • News
    • Events
    • Hertford history
    • Rare books & Archives
    • International Programmes
    • Conferences & events
    • Governance & legal
    • Vacancies
    • Visit us
    • Contact us
  • Hertford Intranet
  • International Programmes
    • International Programmes
    • Directors’ welcome
    • Our programmes
    • Our partnerships
    • Life in Oxford
    • Hertford in Asia
    • How to apply
  • Alumni
    • Alumni
    • Hertford today
    • Meet the Hertfordians
    • Publications
    • Alumni societies
    • Alumni FAQs
    • Update your details
    • Meet the Development team
  • Support us
    • Support us
    • Give to Hertford
    • Fundraising priorities
    • Leave a legacy
    • For donors
  • Contact us
xmlns:xlink="http://www.w3.org/1999/xlink">
  • Hertford Intranet
  • International Programmes
    • International Programmes
    • Directors’ welcome
    • Our programmes
    • Our partnerships
    • Life in Oxford
    • Hertford in Asia
    • How to apply
  • Alumni
    • Alumni
    • Hertford today
    • Meet the Hertfordians
    • Publications
    • Alumni societies
    • Alumni FAQs
    • Update your details
    • Meet the Development team
  • Support us
    • Support us
    • Give to Hertford
    • Fundraising priorities
    • Leave a legacy
    • For donors
  • Contact us
  • Study here
  • Living here
  • Our people
  • News, events and more

Study here  ›

  • Undergraduates
  • Graduates
  • Visiting students
  • Outreach with schools and colleges

Living here  ›

  • Where you will live
  • Eating here
  • Library & resources
  • Chapel & Faith
  • Do what you love
  • Help is on hand

News, events and more  ›

  • Our vision for 2030
  • News
  • Events
  • Hertford history
  • Rare books & Archives
  • International Programmes
  • Conferences & events
  • Governance & legal
  • Vacancies
  • Visit us
  • Contact us
Home / Our people / Dr Andreas Galanis

Dr Andreas Galanis

Tutorial Fellow in Computer Science

Associate Professor in Computer Science

andreas.galanis@hertford.ox.ac.uk

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

Academic

  • Principal

  • Tutors & Lecturers

  • Visiting Student Lecturers

  • Professorial & Research Fellows

  • Visiting Fellows

  • Emeritus Fellows

Study here

  • Undergraduates
  • Graduates
  • Visiting students
  • Outreach with schools and colleges

Living here

  • Where you will live
  • Eating here
  • Library & resources
  • Chapel & Faith
  • Do what you love
  • Help is on hand

Our people

  • Our people

News, events and more

  • Our vision for 2030
  • News
  • Events
  • Hertford history
  • Rare books & Archives
  • International Programmes
  • Conferences & events
  • Governance & legal
  • Vacancies
  • Visit us
  • Contact us

Follow us

Hertford College
Catte Street
Oxford
OX1 3BW


Tel: +44 (0)1865 279 400

© 2025 Hertford College Registered Charity No. 1137527

  • Contact us
  • Privacy
  • Legal

Site by Franks and Franks