research
∙
06/26/2023
Approximate Counting for Spin Systems in Sub-Quadratic Time
We present two approximate counting algorithms with O(n^2-c/ε^2) running...
share
research
∙
02/13/2023
On the Mixing Time of Glauber Dynamics for the Hard-core and Related Models on G(n,d/n)
We study the single-site Glauber dynamics for the fugacity λ, Hard-core ...
research
∙
11/07/2022
Towards derandomising Markov chain Monte Carlo
We present a new framework to derandomise certain Markov chain Monte Car...
research
∙
08/01/2022
A simple polynomial-time approximation algorithm for the total variation distance between two product distributions
We give a simple polynomial-time approximation algorithm for the total v...
research
∙
05/04/2022
Sampling from the ferromagnetic Ising model with external fields
We study the sampling problem for ferromagnetic Ising models with consis...
research
∙
03/15/2022
Optimal mixing for two-state anti-ferromagnetic spin systems
We prove an optimal Ω(n^-1) lower bound for modified log-Sobolev (MLS) c...
research
∙
02/11/2022
Improved bounds for randomly colouring simple hypergraphs
We study the problem of sampling almost uniform proper q-colourings in k...
research
∙
11/04/2021
Optimal Mixing Time for the Ising Model in the Uniqueness Regime
We prove an optimal O(n log n) mixing time of the Glauber dynamics for t...
research
∙
05/31/2021
Rapid mixing of Glauber dynamics via spectral independence for all degrees
We prove an optimal Ω(n^-1) lower bound on the spectral gap of Glauber d...
research
∙
11/08/2020
Sampling Constraint Satisfaction Solutions in the Local Lemma Regime
We give a Markov chain based algorithm for sampling almost uniform solut...
research
∙
07/16/2020
Rapid mixing from spectral independence beyond the Boolean domain
We extend the notion of spectral independence (introduced by Anari, Liu,...
research
∙
11/04/2019
Fast sampling and counting k-SAT solutions in the local lemma regime
We give new algorithms based on Markov chains to sample and approximatel...
research
∙
07/13/2019
Perfect sampling from spatial mixing
We show that strong spatial mixing with a rate faster than the growth of...
research
∙
04/26/2019
Dynamic MCMC Sampling
The Markov chain Monte Carlo (MCMC) methods are the primary tools for sa...
research
∙
04/01/2019
Fully-Asynchronous Distributed Metropolis Sampler with Optimal Speedup
The Metropolis-Hastings algorithm is a fundamental Markov chain Monte Ca...
research
∙
07/17/2018
Local Rejection Sampling with Soft Filters
We study a new LLL-like framework for rejection sampling, which naturall...
research
∙
02/20/2018
Distributed Symmetry Breaking in Sampling (Optimal Distributed Randomly Coloring with Fewer Colors)
We examine the problem of almost-uniform sampling proper q-colorings of ...
research
∙
02/19/2018