Markov Chain Monte Carlo (MCMC) algorithms are a widely-used algorithmic tool for
sampling from high-dimensional distributions, a notable example is the equilibirum …

Single-site dynamics are canonical Markov chain based algorithms for sampling from high-
dimensional distributions, such as the Gibbs distributions of graphical models. We introduce …

The local computation of Linial [FOCS'87] and Naor and Stockmeyer [STOC'93] concerns
with the question of whether a locally definable distributed computing problem can be …

We provide a perfect sampling algorithm for the hard-sphere model on subsets of $\mathbb
{R}^ d $ with expected running time linear in the volume under the assumption of strong …

We introduce a new perfect sampling technique that can be applied to general Gibbs
distributions and runs in linear time if the correlation decays faster than the neighborhood …

The single-site dynamics are a canonical class of Markov chains for sampling from high-
dimensional probability distributions, eg the ones represented by graphical models. We give …

We examine the problem of almost-uniform sampling proper $ q $-colorings of a graph
whose maximum degree is $\Delta $. A famous result, discovered independently by Jerrum …

Constraint satisfaction problems (CSPs) and data stream models are two powerful
abstractions to capture a wide variety of problems arising in different domains of computer …

Constraint satisfaction problems (CSPs) and data stream models are two powerful
abstractions to capture a wide variety of problems arising in different domains of computer …

We present the first sublinear round algorithm for approximately sampling uniform spanning
trees in the CongestedClique model of distributed computing. In particular, our algorithm …