Eric Vigoda

Kuikui Liu

SIAM J. Comput., February, 2023

Spectral Independence Lecture Notes.

[BibT_eX]

[DOI]

CoRR, 2023

Improved Distributed Algorithms for Random Colorings.

[BibT_eX]

[DOI]

Charlie Carlson

Daniel Frishberg

Proceedings of the 27th International Conference on Principles of Distributed Systems, 2023

Counting and Sampling Labeled Chordal Graphs in Polynomial Time.

[BibT_eX]

[DOI]

Úrsula Hébert-Johnson

Daniel Lokshtanov

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2023

2022

Identity Testing for High-Dimensional Distributions via Entropy Tensorization.

[BibT_eX]

[DOI]

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

On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization.

[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

Leslie Ann Goldberg

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

2021

Fast algorithms at low temperatures via Markov chains.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2021

Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2021

Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion.

[BibT_eX]

[DOI]

Kuikui Liu

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Entropy decay in the Swendsen-Wang dynamics on ℤd.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Rapid Mixing for Colorings via Spectral Independence.

[BibT_eX]

[DOI]

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

Spectral Independence via Stability and Applications to Holant-Type Problems.

[BibT_eX]

[DOI]

Kuikui Liu

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

The Swendsen-Wang Dynamics on Trees.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2021

2020

Random Walks on Small World Networks.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

Structure Learning of H-Colorings.

[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

Swendsen-Wang dynamics for general graphs in the tree uniqueness region.

[BibT_eX]

[DOI]

Antonio Blanca

Random Struct. Algorithms, 2020

Lower Bounds for Testing Graphical Models: Colorings and Antiferromagnetic Ising Models.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 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

Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

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

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2019

Spatial mixing and nonlocal Markov chains.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2019

Improved Strong Spatial Mixing for Colorings on Trees.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

Random-Cluster Dynamics in Z2: Rapid Mixing with General Boundary Conditions.

[BibT_eX]

[DOI]

Antonio Blanca

Reza Gheissari

Proceedings of the Approximation, 2019

2018

Sampling Random Colorings of Sparse Random Graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Spatial Mixing and Non-local Markov chains.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

On Counting Perfect Matchings in General Graphs.

[BibT_eX]

[DOI]

John Wilmes

Proceedings of the LATIN 2018: Theoretical Informatics, 2018

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

#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

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

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2016

2015

Improved Bounds on the Phase Transition for the Hard-Core Model in 2 Dimensions.

[BibT_eX]

[DOI]

Juan Carlos Vera

Linji Yang

SIAM J. Discret. Math., 2015

Randomly coloring planar graphs with fewer colors than the maximum degree.

[BibT_eX]

[DOI]

Juan Carlos Vera

Random Struct. Algorithms, 2015

Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region.

[BibT_eX]

[DOI]

J. ACM, 2015

2014

Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 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]

CoRR, 2013

2012

A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions.

[BibT_eX]

[DOI]

Santosh S. Vempala

SIAM J. Comput., 2012

Negative Examples for Sequential Importance Sampling of Binary Contingency Tables.

[BibT_eX]

[DOI]

Algorithmica, 2012

2011

Fast Convergence of Markov Chain Monte Carlo Algorithms for Phylogenetic Reconstruction with Homogeneous Data on Closely Related Species.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2011

Reconstruction for Colorings on Trees.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2011

Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

An FPTAS for #Knapsack and Related Counting Problems.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Fast Convergence of MCMC Algorithms for Phylogenetic Reconstruction with Homogeneous Data on Closely Related Species

[BibT_eX]

[DOI]

CoRR, 2010

Phase Transition for the Mixing Time of the Glauber Dynamics for Coloring Regular Trees.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009

Adaptive simulated annealing: A near-optimal connection between sampling and counting.

[BibT_eX]

[DOI]

Santosh S. Vempala

J. ACM, 2009

2008

Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

Mutations of Different Molecular Origins Exhibit Contrasting Patterns of Regional Substitution Rate Variation.

[BibT_eX]

[DOI]

PLoS Comput. Biol., 2008

Random Bichromatic Matchings.

[BibT_eX]

[DOI]

Algorithmica, 2008

2007

Variable length path coupling.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2007

Sampling binary contingency tables with a greedy start.

[BibT_eX]

[DOI]

Ivona Bezáková

Nayantara Bhatnagar

Random Struct. Algorithms, 2007

Phylogeny of Mixture Models: Robustness of Maximum Likelihood and Non-Identifiable Distributions.

[BibT_eX]

[DOI]

J. Comput. Biol., 2007

2006

Randomly coloring sparse random graphs with fewer colors than the maximum degree.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2006

2005

Torpid mixing of the Wang-Swendsen-Kotecký algorithm for sampling colorings.

[BibT_eX]

[DOI]

Tomasz Luczak

J. Discrete Algorithms, 2005

Coupling with the stationary distribution and improved sampling for colorings and independent sets.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004

Mixing in time and space for lattice spin systems: A combinatorial view.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2004

A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.

[BibT_eX]

[DOI]

Alistair Sinclair

J. ACM, 2004

Randomly coloring constant degree graphs

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

2003

A Non-Markovian Coupling for Randomly Sampling Colorings.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2001

A Note on the Glauber Dynamics for Sampling Independent Sets.

[BibT_eX]

[DOI]

Electron. J. Comb., 2001

A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries.

[BibT_eX]

[DOI]

Alistair Sinclair

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs.

[BibT_eX]

[DOI]

Martin E. Dyer

Proceedings of the Graphs, 2001

2000

A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2000

1999

Fast convergence of the Glauber dynamics for sampling independent sets.

[BibT_eX]

[DOI]

Michael Luby

Random Struct. Algorithms, 1999

Improved Bounds for Sampling Colorings.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1997

Approximately Counting Up To Four (Extended Abstract).

[BibT_eX]

[DOI]

Michael Luby

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

1996

General upper bounds for covering numbers.

[BibT_eX]

Anant P. Godbole

Sandra E. Thompson