research
∙
09/14/2023
Improved Distributed Algorithms for Random Colorings
Markov Chain Monte Carlo (MCMC) algorithms are a widely-used algorithmic...
share
research
∙
08/18/2023
Counting and Sampling Labeled Chordal Graphs in Polynomial Time
We present the first polynomial-time algorithm to exactly compute the nu...
research
∙
07/25/2023
Spectral Independence Lecture Notes
These are self-contained lecture notes for spectral independence. For an...
research
∙
07/15/2023
Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees
We study the mixing time of the single-site update Markov chain, known a...
research
∙
07/19/2022
Identity Testing for High-Dimensional Distributions via Entropy Tensorization
We present improved algorithms and matching statistical and computationa...
research
∙
06/23/2022
Approximating observables is as hard as counting
We study the computational complexity of estimating local observables fo...
research
∙
02/11/2022
Metastability of the Potts ferromagnet on random regular graphs
We study the performance of Markov chains for the q-state ferromagnetic ...
research
∙
06/07/2021
Spectral Independence via Stability and Applications to Holant-Type Problems
This paper formalizes connections between stability of polynomials and c...
research
∙
05/04/2021
Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness Region
For spin systems, such as the q-colorings and independent-set models, ap...
research
∙
03/12/2021
On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization
For general spin systems, we prove that a contractive coupling for any l...
research
∙
11/04/2020
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion
We prove an optimal mixing time bound on the single-site update Markov c...
research
∙
07/16/2020
The Swendsen-Wang Dynamics on Trees
The Swendsen-Wang algorithm is a sophisticated, widely-used Markov chain...
research
∙
07/16/2020
Rapid Mixing for Colorings via Spectral Independence
The spectral independence approach of Anari et al. (2020) utilized recen...
research
∙
04/22/2020
Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models
We study identity testing for restricted Boltzmann machines (RBMs), and ...
research
∙
04/20/2020
The complexity of approximating averages on bounded-degree graphs
We prove that, unless P=NP, there is no polynomial-time algorithm to app...
research
∙
04/20/2020
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
For general antiferromagnetic 2-spin systems, including the hardcore mod...
research
∙
09/16/2019
Improved Strong Spatial Mixing for Colorings on Trees
Strong spatial mixing (SSM) is a form of correlation decay that has play...
research
∙
01/22/2019
Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
We study the identity testing problem in the context of spin systems or ...
research
∙
01/20/2019
Markov chains for the hard-core model via polymer models
Jenssen, Keevash and Perkins give an FPTAS and an efficient sampling alg...
research
∙
06/12/2018
Swendsen-Wang Dynamics for General Graphs in the Tree Uniqueness Region
The Swendsen-Wang dynamics is a popular algorithm for sampling from the ...
research
∙
04/22/2018
Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs
We consider the problem of sampling from the Potts model on random regul...
research
∙
12/20/2017
On Counting Perfect Matchings in General Graphs
Counting perfect matchings has played a central role in the theory of co...
research
∙
08/17/2017
Structure Learning of H-colorings
We study the structure learning problem for graph homomorphisms, commonl...
research
∙
04/06/2017