Showing cs.DCShow all
3 papers · 1 filter
cs.DC2025
Congested Clique Counting for Local Gibbs Distributions
Joshua Z. Sobel
There are well established reductions between combinatorial sampling and counting problems (Jerrum, Valiant, Vazirani TCS 1986). Building off of a very recent parallel algorithm ut…
cs.DC2024
Sublinear-Time Sampling of Spanning Trees in the Congested Clique
Sriram V. Pemmaraju, Sourya Roy, Joshua Z. Sobel
We present the first sublinear-in- round algorithm for sampling an approximately uniform spanning tree of an -vertex graph in the CongestedClique model of distributed computi…
cs.DC2023
Exact Distributed Sampling
Sriram V. Pemmaraju, Joshua Z. Sobel
Fast distributed algorithms that output a feasible solution for constraint satisfaction problems, such as maximal independent sets, have been heavily studied. There has been much l…