Parallel Sampling via Counting

I will talk about a new result that shows how to speed up sampling from an arbitrary distribution on a product space [q]^n, given oracle access to conditional marginals, as in any-order autoregressive models. The algorithm takes n^{2/3} polylog(n, q) parallel time, the first sublinear-in-n bound for arbitrary distributions. We also 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. Joint work with Aviad Rubinstein and Ruiquan Gao.