6 citations · 15 across the 23 of their papers we have counts for
15 papers · 1 filter
Parallel Sampling via Autospeculation
Nima Anari, Carlo Baronio, CJ Chen +4
We present parallel algorithms to accelerate sampling via counting in two settings: any-order autoregressive models and denoising diffusion models. An any-order autoregressive mode…
Fast parallel sampling under isoperimetry
Nima Anari, Sinho Chewi, Thuy-Duong Vuong
We show how to sample in parallel from a distribution over that satisfies a log-Sobolev inequality and has a smooth log-density, by parallelizing the Langevin (re…
Optimal mixing of the down-up walk on independent sets of a given size
Vishesh Jain, Marcus Michelen, Huy Tuan Pham +1
Let be a graph on vertices of maximum degree . We show that, for any , the down-up walk on independent sets of size mixes in time $O_{Δ,δ}(k\…
Composable Coresets for Constrained Determinant Maximization and Beyond
Sepideh Mahabadi, Thuy-Duong Vuong
We study algorithms for construction of composable coresets for the task of Determinant Maximization under partition constraint. Given a point set that is p…
On the Complexity of Sampling Redistricting Plans
Moses Charikar, Paul Liu, Tianyu Liu +1
A crucial task in the political redistricting problem is to sample redistricting plans i.e. a partitioning of the graph of census blocks into districts. We show that Recombination…
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence
Nima Anari, Yang P. Liu, Thuy-Duong Vuong
We design fast algorithms for repeatedly sampling from strongly Rayleigh distributions, which include random spanning tree distributions and determinantal point processes. For a gr…