research
∙
07/27/2023
Correlation decay up to the sampling threshold in the local lemma regime
We study the decay of correlation between locally constrained independen...
share
research
∙
04/29/2023
Uniqueness and Rapid Mixing in the Bipartite Hardcore Model
We characterize the uniqueness condition in the hardcore model for bipar...
research
∙
12/30/2022
Deterministic counting Lovász local lemma beyond linear programming
We give a simple combinatorial algorithm to deterministically approximat...
research
∙
11/07/2022
Towards derandomising Markov chain Monte Carlo
We present a new framework to derandomise certain Markov chain Monte Car...
research
∙
07/29/2022
Locally-iterative (Δ+1)-Coloring in Sublinear (in Δ) Rounds
Distributed graph coloring is one of the most extensively studied proble...
research
∙
04/04/2022
Sampling Lovász Local Lemma For General Constraint Satisfaction Solutions In Near-Linear Time
We give a fast algorithm for sampling uniform solutions of general const...
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
∙
01/30/2022
Polynomial-Time Approximation of Zero-Free Partition Functions
Zero-free based algorithm is a major technique for deterministic approxi...
research
∙
11/07/2021
Simple Parallel Algorithms for Single-Site Dynamics
The single-site dynamics are a canonical class of Markov chains for samp...
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
∙
04/26/2020
Succinct Filters for Sets of Unknown Sizes
The membership problem asks to maintain a set S⊆[u], supporting insertio...
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