Sampling Arborescences in Parallel
summary
Claims an RNC sampler that outputs a rooted arborescence from a weighted digraph with probability proportional to product of edge weights, running in polylog time with polynomial processors. Method combines Aldous–Broder reduction to random-walk-first-visit edges, Tang's doubling trick to generate long walk transcripts in parallel, Eulerian and loose-cycle reductions, hierarchical clustering, and shortcutting via linear algebra to compute exit probabilities. It builds a parallel partial-transcript generator that with high probability contains all first-visit edges (uses an O(n^2) bound per cluster) and succeeds.
AI-written summary · about