Parallel Discrete Sampling via Continuous Walks
summary
Claims first polylogarithmic-time sampling (quasi-RNC or RNC under extra stability) for determinantal point processes, spanning trees and directed Eulerian tours, while planar perfect matchings remain excluded. Method convolves discrete measures with Gaussians to make them log-concave, computes their pdfs from determinant-based Laplace-transform counting oracles, and runs a parallelized stochastic-localization / diffusion sampler using Picard iterations. A key technical condition is transport stability (Wasserstein Lipschitzness of exponential tilts).
AI-written summary · about