Parallel sampling via counting

I will talk about parallelization of sampling algorithms. The main focus of the talk will be a new result, where we show how to speed up sampling from an arbitrary distribution on a product space [q]^n, given oracle access to conditional marginals. Our algorithm takes roughly n^{2/3} polylog(n, q) parallel time, the first sublinear-in-n bound for arbitrary distributions. This suggests a roughly n^{1/3}-factor speedup is possible for sampling in any-order autoregressive models. We show a lower bound of n^{1/3} on the parallel runtime of any algorithm, putting the complexity firmly in the sublinear but polynomially large territory. Time permitting, I will also discuss results and conjectures about parallelization of other sampling algorithms, including some based on stochastic localization.

This is based on joint work with Aviad Rubinstein and Ruiquan Gao.