4 papers
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…
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…
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…
AWLCO: All-Window Length Co-Occurrence
Joshua Sobel, Noah Bertram, Chen Ding +2
Analyzing patterns in a sequence of events has applications in text analysis, computer programming, and genomics research. In this paper, we consider the all-window-length analysis…