Andreas Galanis

Alkis Kalavasis

Anthimos Vardis Kandiros

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 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]

Andrés Herrera-Poyatos

SIAM J. Discret. Math., September, 2022

Fast mixing via polymers for random graphs with unbounded degree.

[BibT_eX]

[DOI]

James Stewart

Inf. Comput., 2022

Fast sampling of satisfying assignments from random k-SAT.

[BibT_eX]

[DOI]

Heng Guo

Andrés Herrera-Poyatos

CoRR, 2022

The complexity of approximating the complex-valued Potts model.

[BibT_eX]

[DOI]

Andrés Herrera-Poyatos

Comput. Complex., 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

2021

Fast Algorithms for General Spin Systems on Bipartite Expanders.

[BibT_eX]

[DOI]

James Stewart

ACM Trans. Comput. Theory, 2021

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

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2021

Counting Solutions to Random CNF Formulas.

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

Fast algorithms at low temperatures via Markov chains.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2021

Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

Kuan Yang

J. Comput. Syst. Sci., 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

2020

Random Walks on Small World Networks.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

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

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2020

Inapproximability of the Independent Set Polynomial in the Complex Plane.

[BibT_eX]

[DOI]

SIAM J. Comput., 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

Approximation via Correlation Decay When Strong Spatial Mixing Fails.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

Swendsen-Wang algorithm on the mean-field Potts model.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2019

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

[BibT_eX]

[DOI]

James Stewart

CoRR, 2019

Improved Strong Spatial Mixing for Colorings on Trees.

[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

2017

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

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2017

Amplifiers for the Moran Process.

[BibT_eX]

[DOI]

J. ACM, 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

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

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

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

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 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

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

2014

Improved inapproximability results for counting independent sets in the hard-core model.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2014

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

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

2013

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

[BibT_eX]

[DOI]