Andreas Galanis

Publication Activity (10 Years)

Years Active: 2011-2024
Publications (10 Years): 75

Top Topics

Bipartite Graph

Independent Set

Constraint Satisfaction

Top Venues

Publications

Andreas Galanis, Alkis Kalavasis, Anthimos Vardis Kandiros
On Sampling from Ising Models with Spectral Constraints. CoRR (2024)
Andreas Galanis, Alkis Kalavasis, Anthimos Vardis Kandiros
Learning Hard-Constrained Models with One Sample. SODA (2024)
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic
Fast Sampling via Spectral Independence Beyond Bounded-degree Graphs. ACM Trans. Algorithms 20 (1) (2024)
Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic
Implementations and the independent set polynomial below the Shearer threshold. Theor. Comput. Sci. 939 (2023)
Andreas Galanis, Leslie Ann Goldberg, Paulina Smolarova
Sampling from the Random Cluster Model on Random Regular Graphs at All Temperatures via Glauber Dynamics. APPROX/RANDOM (2023)
Andreas Galanis, Leslie Ann Goldberg, Paulina Smolarova
Sampling from the random cluster model on random regular graphs at all temperatures via Glauber dynamics. CoRR (2023)
Andreas Galanis, Alkis Kalavasis, Anthimos Vardis Kandiros
Learning Hard-Constrained Models with One Sample. CoRR (2023)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Approximating observables is as hard as counting. CoRR (2022)
Andreas Galanis, Leslie Ann Goldberg, James Stewart
Fast mixing via polymers for random graphs with unbounded degree. Inf. Comput. 285 (Part) (2022)
Andreas Galanis, Heng Guo, Jiaheng Wang
Inapproximability of Counting Hypergraph Colourings. ACM Trans. Comput. Theory 14 (3-4) (2022)
Andreas Galanis, Leslie Ann Goldberg, Andrés Herrera-Poyatos
The complexity of approximating the complex-valued Potts model. Comput. Complex. 31 (1) (2022)
Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Andrés Herrera-Poyatos
Fast sampling of satisfying assignments from random k-SAT. CoRR (2022)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Approximating Observables Is as Hard as Counting. ICALP (2022)
Amin Coja-Oghlan, Andreas Galanis, Leslie Ann Goldberg, Jean Bernoulli Ravelomanana, Daniel Stefankovic, Eric Vigoda
Metastability of the Potts Ferromagnet on Random Regular Graphs. ICALP (2022)
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic
Fast Sampling via Spectral Independence Beyond Bounded-Degree Graphs. ICALP (2022)
Andreas Galanis, Leslie Ann Goldberg, Andrés Herrera-Poyatos
The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs. SIAM J. Discret. Math. 36 (3) (2022)
Zongchen Chen, Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness Region. SODA (2022)
Amin Coja-Oghlan, Andreas Galanis, Leslie Ann Goldberg, Jean Bernoulli Ravelomanana, Daniel Stefankovic, Eric Vigoda
Metastability of the Potts ferromagnet on random regular graphs. CoRR (2022)
Andreas Galanis, Leslie Ann Goldberg, James Stewart
Fast mixing via polymers for random graphs with unbounded degree. CoRR (2021)
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic
The Complexity of Approximating the Matching Polynomial in the Complex Plane. ACM Trans. Comput. Theory 13 (2) (2021)
Andreas Galanis, Leslie Ann Goldberg, Andrés Herrera-Poyatos
The complexity of approximating the complex-valued Ising model on bounded degree graphs. CoRR (2021)
Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Kuan Yang
Counting Solutions to Random CNF Formulas. SIAM J. Comput. 50 (6) (2021)
Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Will Perkins, James Stewart, Eric Vigoda
Fast algorithms at low temperatures via Markov chains. Random Struct. Algorithms 58 (2) (2021)
Zongchen Chen, Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Rapid Mixing for Colorings via Spectral Independence. SODA (2021)
Andreas Galanis, Heng Guo, Jiaheng Wang
Inapproximability of counting hypergraph colourings. CoRR (2021)
Zongchen Chen, Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness Region. CoRR (2021)
Andreas Galanis, Leslie Ann Goldberg, James Stewart
Fast Mixing via Polymers for Random Graphs with Unbounded Degree. APPROX-RANDOM (2021)
Andreas Galanis, Leslie Ann Goldberg, Kuan Yang
Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems. J. Comput. Syst. Sci. 115 (2021)
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic
Fast sampling via spectral independence beyond bounded-degree graphs. CoRR (2021)
Andreas Galanis, Leslie Ann Goldberg, James Stewart
Fast Algorithms for General Spin Systems on Bipartite Expanders. ACM Trans. Comput. Theory 13 (4) (2021)
Pjotr Buys, Andreas Galanis, Viresh Patel, Guus Regts
Lee-Yang zeros and the complexity of the ferromagnetic Ising Model on bounded-degree graphs. SODA (2021)
Andreas Galanis, Leslie Ann Goldberg, James Stewart
Fast algorithms for general spin systems on bipartite expanders. CoRR (2020)
Antonio Blanca, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic, Eric Vigoda, Kuan Yang
Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs. SIAM J. Discret. Math. 34 (1) (2020)
Andreas Galanis, Leslie Ann Goldberg, Andrés Herrera-Poyatos
The Complexity of Approximating the Complex-Valued Potts Model. MFCS (2020)
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic
Inapproximability of the Independent Set Polynomial in the Complex Plane. SIAM J. Comput. 49 (5) (2020)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
The complexity of approximating averages on bounded-degree graphs. FOCS (2020)
Andreas Galanis, Leslie Ann Goldberg, Andrés Herrera-Poyatos
The complexity of approximating the complex-valued Potts model. CoRR (2020)
Pjotr Buys, Andreas Galanis, Viresh Patel, Guus Regts
Lee-Yang zeros and the complexity of the ferromagnetic Ising Model on bounded-degree graphs. CoRR (2020)
Zongchen Chen, Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Rapid Mixing for Colorings via Spectral Independence. CoRR (2020)
Andreas Galanis, Leslie Ann Goldberg, James Stewart
Fast Algorithms for General Spin Systems on Bipartite Expanders. MFCS (2020)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
The complexity of approximating averages on bounded-degree graphs. CoRR (2020)
Martin E. Dyer, Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum, Eric Vigoda
Random Walks on Small World Networks. ACM Trans. Algorithms 16 (3) (2020)
Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Kuan Yang
Counting Solutions to Random CNF Formulas. ICALP (2020)
Andreas Galanis, Leslie Ann Goldberg, James Stewart
A note on the high-fugacity hard-core model on bounded-degree bipartite expander graphs. CoRR (2019)
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Daniel Stefankovic
Approximation via Correlation Decay When Strong Spatial Mixing Fails. SIAM J. Comput. 48 (2) (2019)
Charilaos Efthymiou, Andreas Galanis, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda
Improved Strong Spatial Mixing for Colorings on Trees. CoRR (2019)
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic
The Complexity of Approximating the Matching Polynomial in the Complex Plane. ICALP (2019)
Charilaos Efthymiou, Andreas Galanis, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda
Improved Strong Spatial Mixing for Colorings on Trees. APPROX-RANDOM (2019)
Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Kuan Yang
Counting solutions to random CNF formulas. CoRR (2019)
Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Will Perkins, James Stewart, Eric Vigoda
Fast Algorithms at Low Temperatures via Markov Chains. APPROX-RANDOM (2019)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Swendsen-Wang algorithm on the mean-field Potts model. Random Struct. Algorithms 54 (1) (2019)
Antonio Blanca, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic, Eric Vigoda, Kuan Yang
Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs. CoRR (2018)
Andreas Galanis, Leslie Ann Goldberg, Kuan Yang
Uniqueness for the 3-State Antiferromagnetic Potts Model on the Tree. CoRR (2018)
Antonio Blanca, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic, Eric Vigoda, Kuan Yang
Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs. APPROX-RANDOM (2018)
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic
The complexity of approximating the matching polynomial in the complex plane. CoRR (2018)
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic
Inapproximability of the independent set polynomial in the complex plane. STOC (2018)
Andreas Galanis, Leslie Ann Goldberg, Kuan Yang
Approximating Partition Functions of Bounded-Degree Boolean Counting Constraint Satisfaction Problems. ICALP (2017)
Sejun Park, Yunhun Jang, Andreas Galanis, Jinwoo Shin, Daniel Stefankovic, Eric Vigoda
Rapid Mixing Swendsen-Wang Sampler for Stochastic Partitioned Attractive Models. AISTATS (2017)
Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum
-Colorings. ACM Trans. Comput. Theory 9 (2) (2017)
Martin E. Dyer, Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum, Eric Vigoda
Random Walks on Small World Networks. CoRR (2017)
Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg, John Lapinskas, David Richerby
Amplifiers for the Moran Process. J. ACM 64 (1) (2017)
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic
Inapproximability of the independent set polynomial in the complex plane. CoRR (2017)
Sejun Park, Yunhun Jang, Andreas Galanis, Jinwoo Shin, Daniel Stefankovic, Eric Vigoda
Rapid Mixing Swendsen-Wang Sampler for Stochastic Partitioned Attractive Models. CoRR (2017)
Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic
Inapproximability of the Independent Set Polynomial Below the Shearer Threshold. ICALP (2017)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda, Linji Yang
Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results. SIAM J. Comput. 45 (6) (2016)
Andreas Galanis, Leslie Ann Goldberg, Kuan Yang
Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems. CoRR (2016)
Andreas Galanis, Leslie Ann Goldberg
The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs. Inf. Comput. 251 (2016)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models. Comb. Probab. Comput. 25 (4) (2016)
Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum
Approximately Counting H-Colorings is $\#\mathrm{BIS}$-Hard. SIAM J. Comput. 45 (3) (2016)
Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum
A Complexity Trichotomy for Approximately Counting List H-Colourings. ICALP (2016)
Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic
Inapproximability of the independent set polynomial below the Shearer threshold. CoRR (2016)
Andreas Galanis, Leslie Ann Goldberg
-uniform bounded-degree hypergraphs. SODA (2016)
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Daniel Stefankovic
Approximation via Correlation Decay When Strong Spatial Mixing Fails. ICALP (2016)
Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic, Eric Vigoda
#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. J. Comput. Syst. Sci. 82 (5) (2016)
Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg, John Lapinskas, David Richerby
Amplifiers for the Moran Process. ICALP (2016)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Swendsen-Wang Algorithm on the Mean-Field Potts Model. CoRR (2015)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region. J. ACM 62 (6) (2015)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Swendsen-Wang Algorithm on the Mean-Field Potts Model. APPROX-RANDOM (2015)
Andreas Galanis, Leslie Ann Goldberg
The complexity of approximately counting in 2-spin systems on $k$-uniform bounded-degree hypergraphs. CoRR (2015)
Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg, John Lapinskas, David Richerby
Amplifiers for the Moran Process. CoRR (2015)
Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum
Approximately Counting H-Colourings is #\mathrm BIS # BIS -Hard. ICALP (1) (2015)
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Daniel Stefankovic
Approximation via Correlation Decay when Strong Spatial Mixing Fails. CoRR (2015)
Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum
Approximately Counting H-Colourings is #BIS-Hard. CoRR (2015)
Andreas Galanis, Qi Ge, Daniel Stefankovic, Eric Vigoda, Linji Yang
Improved inapproximability results for counting independent sets in the hard-core model. Random Struct. Algorithms 45 (1) (2014)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda, Linji Yang
Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results. APPROX-RANDOM (2014)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region. STOC (2014)
Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic, Eric Vigoda
#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region. APPROX-RANDOM (2014)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
BIS-Hardness for Ferromagnetic Potts in the Ordered Phase and Related Results. CoRR (2013)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Inapproximability for Antiferromagnetic Spin Systems in the Tree Non-Uniqueness Region CoRR (2013)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models CoRR (2012)
Andreas Galanis, Qi Ge, Daniel Stefankovic, Eric Vigoda, Linji Yang
Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model. APPROX-RANDOM (2011)
Andreas Galanis, Qi Ge, Daniel Stefankovic, Eric Vigoda, Linji Yang
Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model CoRR (2011)