Parallel Discrete Sampling via Continuous Walks

Nima Anari (Stanford) presents a framework for sampling from discrete distributions on the hypercube $\{\pm 1\}^n$. The framework samples continuous distributions supported on $\mathbb{R}^n$ obtained by convolution with spherical Gaussians. He and collaborators Yizhi Huang, Tianyu Liu, Thuy-Duong Vuong, Brian Xu, and Katherine Yu obtain the first polylogarithmic-time sampling algorithms for determinantal point processes, directed Eulerian tours, and more.