Parallel Discrete Sampling via Continuous Walks

I will talk about a framework for sampling discrete objects by employing continuous-space sampling algorithms. This framework can be thought of as a sampling-to-counting reduction, which, unlike the classic reduction of Jerrum-Valiant-Vazirani, can be parallelized in certain interesting cases. Our framework gives the first algorithm for sampling in polylogarithmic (parallel) time from distributions like determinantal point processes and directed Eulerian tours. I will highlight the main ideas on two combinatorial distributions: uniformly random spanning trees, and uniformly random Eulerian tours in a directed Eulerian graph.

 

Joint work with Yizhi Huang, Tianyu Liu, Thuy-Duong Vuong, Brian Xu, and Katherine Yu.