Andreas Galanis

Xusheng Zhang

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

Low-Temperature Sampling on Sparse Random Graphs.

[BibT_eX]

[DOI]

Paulina Smolarova

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

2024

Fast Sampling of Satisfying Assignments from Random $\boldsymbol{k}$-SAT with Applications to Connectivity.

[BibT_eX]

[DOI]

Nitya Mani

Ankur Moitra

SIAM J. Discret. Math., 2024

Planting and MCMC Sampling from the Potts model.

[BibT_eX]

[DOI]

Paulina Smolarova

CoRR, 2024

Learning Hard-Constrained Models with One Sample.

[BibT_eX]

[DOI]

Alkis Kalavasis

Anthimos Vardis Kandiros

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

On Sampling from Ising Models with Spectral Constraints.

[BibT_eX]

[DOI]

Alkis Kalavasis

Anthimos Vardis Kandiros

Proceedings of the Approximation, 2024

2023

Implementations and the independent set polynomial below the Shearer threshold.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2023

Sampling from the Random Cluster Model on Random Regular Graphs at All Temperatures via Glauber Dynamics.

[BibT_eX]

[DOI]

Paulina Smolarova

Proceedings of the Approximation, 2023

2022

Inapproximability of Counting Hypergraph Colourings.

[BibT_eX]

[DOI]

Heng Guo

Jiaheng Wang

ACM Trans. Comput. Theory, December, 2022

The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., September, 2022

Fast sampling of satisfying assignments from random k-SAT.

[BibT_eX]

[DOI]

Heng Guo

CoRR, 2022

Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness Region.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Approximating Observables Is as Hard as Counting.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Metastability of the Potts Ferromagnet on Random Regular Graphs.

[BibT_eX]

[DOI]

Amin Coja-Oghlan

Jean Bernoulli Ravelomanana

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Fast Sampling via Spectral Independence Beyond Bounded-Degree Graphs.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

Rapid Mixing for Colorings via Spectral Independence.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Lee-Yang zeros and the complexity of the ferromagnetic Ising Model on bounded-degree graphs.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Fast Mixing via Polymers for Random Graphs with Unbounded Degree.

[BibT_eX]

[DOI]

James Stewart

Proceedings of the Approximation, 2021

2020

Random Walks on Small World Networks.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

Fast Algorithms for General Spin Systems on Bipartite Expanders.

[BibT_eX]

[DOI]

James Stewart

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

The Complexity of Approximating the Complex-Valued Potts Model.

[BibT_eX]

[DOI]

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

Counting Solutions to Random CNF Formulas.

[BibT_eX]

[DOI]

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

The complexity of approximating averages on bounded-degree graphs.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

A note on the high-fugacity hard-core model on bounded-degree bipartite expander graphs.

[BibT_eX]

[DOI]

James Stewart

CoRR, 2019

The Complexity of Approximating the Matching Polynomial in the Complex Plane.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Improved Strong Spatial Mixing for Colorings on Trees.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

Fast Algorithms at Low Temperatures via Markov Chains.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

2018

Uniqueness for the 3-State Antiferromagnetic Potts Model on the Tree.

[BibT_eX]

[DOI]

Kuan Yang

CoRR, 2018

Inapproximability of the independent set polynomial in the complex plane.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2018

2017

A Complexity Trichotomy for Approximately Counting List <i>H</i>-Colorings.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2017

Approximating Partition Functions of Bounded-Degree Boolean Counting Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

Kuan Yang

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Inapproximability of the Independent Set Polynomial Below the Shearer Threshold.

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Rapid Mixing Swendsen-Wang Sampler for Stochastic Partitioned Attractive Models.

[BibT_eX]

[DOI]

Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017

2016

Approximately Counting H-Colorings is $\#\mathrm{BIS}$-Hard.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs.

[BibT_eX]

[DOI]

Inf. Comput., 2016

Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2016

The complexity of approximately counting in 2-spin systems on <i>k</i>-uniform bounded-degree hypergraphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

A Complexity Trichotomy for Approximately Counting List H-Colourings.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Amplifiers for the Moran Process.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Approximation via Correlation Decay When Strong Spatial Mixing Fails.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region.

[BibT_eX]

[DOI]

J. ACM, 2015

Approximately Counting H-Colourings is #BIS-Hard.

[BibT_eX]

[DOI]

CoRR, 2015

Approximately Counting H-Colourings is #\mathrm BIS # BIS -Hard.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Swendsen-Wang Algorithm on the Mean-Field Potts Model.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2015

2014

Phase transitions in the complexity of counting.

[BibT_eX]

[DOI]

PhD thesis, 2014

Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2014

#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2014

2013

BIS-Hardness for Ferromagnetic Potts in the Ordered Phase and Related Results.

[BibT_eX]

[DOI]