We present parallel algorithms to accelerate sampling via counting in two settings: any-order autoregressive models and denoising diffusion models. An any-order autoregressive model accesses a target distribution µ on [q]n through an oracle that provides conditional marginals, while a denoising diffusion model accesses a target distribution µ on ℝn through an oracle that provides conditional means under Gaussian noise. Standard sequential sampling algorithms require Õ(n) time to produce a sample from µ in either setting. We show that, by issuing oracle calls in parallel, the expected sampling time can be reduced to Õ(n1/2). This improves the previous Õ(n2/3) bound for any-order autoregressive models and yields the first parallel speedup for diffusion models in the high-accuracy regime, under the relatively mild assumption that the support of µ is bounded.

Clustering and diversification are two central problems with various applications in machine learning, data mining, and information retrieval. The k-center clustering and k-diversity maximization are two of the most well-studied and widely-used problems in this area. Both problems admit sequential algorithms with optimal approximation factors of 2 in any metric space. However, finding distributed algorithms matching the same optimal approximation ratios has been open for more than a decade, with the best current algorithms having factors at least twice the optimal. In this paper, we settle this open problem by presenting constant-round distributed algorithms for k-center clustering and k-diversity maximization in the massively parallel computation (MPC) model, achieving an approximation factor of 2 + ε in any metric space for any constant ε > 0, which is essentially the best possible considering the lower bound of 2 on the approximability of both these problems. Our algorithms are based on a novel technique for approximating vertex degrees and finding a so-called k-bounded maximal independent set in threshold graphs, using only a constant number of MPC rounds. Other applications of our general technique is also implied, including an almost optimal (3 + ε)-approximation algorithm for the k-supplier problem in any metric space in the MPC model.