Andreas Galanis

104 papers A* 20A 4B 2Journal 68Unranked 9

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