JSJoshua Z. Sobel
Joshua Z. Sobel
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Joshua Z. Sobel has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Sriram V. Pemmaraju
University of Iowa, Iowa City, USA
6 shared publications - Hongyan Ji
The University of Iowa, Iowa City, United States
2 shared publications - Shreyas Pai
IIT Madras, Chennai, India
2 shared publications - Sourya Roy
University of Iowa, Iowa City, USA
2 shared publications - Gopal Pandurangan
University of Houston, Houston, USA
1 shared publication
Latest Publications
- 8 September 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1086
Faster set cover in the MPC model
- 8 September 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1086
Faster set cover in the MPC model
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 402-413
Improved Bounds for Distributed Random Walks and Spanning Trees
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 402-413
Open AccessImproved Bounds for Distributed Random Walks and Spanning Trees
- Open Access
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 337-348
Sublinear-Time Sampling of Spanning Trees in the Congested Clique
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 337-348
Open AccessSublinear-Time Sampling of Spanning Trees in the Congested Clique
- Open Access
- 4 January 2025
- Published by Association for Computing Machinery (ACM)
- p. 144-151
Faster Set Cover in the MPC Model
- 4 January 2025
- Published by Association for Computing Machinery (ACM)
- p. 144-151
Open AccessFaster Set Cover in the MPC Model
- Open Access
Exact Distributed Sampling
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 less research on distributed sampling problems, where one wants to sample from a distribution over all feasible solutions (e.g., uniformly sampling a feasible solution). Recent work (Feng, Sun, Yin PODC 2017; Fischer and Ghaffari DISC 2018; Feng, Hayes, and Yin arXiv 2018) has shown that for some constraint satisfaction problems there are distributed Markov chains that mix in $O(\log n)$ rounds in the classical LOCAL model of distributed computation. However, these methods return samples from a distribution close to the desired distribution, but with some small amount of error. In this paper, we focus on the problem of exact distributed sampling. Our main contribution is to show that these distributed Markov chains in tandem with techniques from the sequential setting, namely coupling from the past and bounding chains, can be used to design $O(\log n)$-round LOCAL model exact sampling algorithms for a class of weighted local constraint satisfaction problems. This general result leads to $O(\log n)$-round exact sampling algorithms that use small messages (i.e., run in the CONGEST model) and polynomial-time local computation for some important special cases, such as sampling weighted independent sets (aka the hardcore model) and weighted dominating sets.Open AccessExact Distributed Sampling
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 less research on distributed sampling problems, where one wants to sample from a distribution over all feasible solutions (e.g., uniformly sampling a feasible solution). Recent work (Feng, Sun, Yin PODC 2017; Fischer and Ghaffari DISC 2018; Feng, Hayes, and Yin arXiv 2018) has shown that for some constraint satisfaction problems there are distributed Markov chains that mix in $O(\log n)$ rounds in the classical LOCAL model of distributed computation. However, these methods return samples from a distribution close to the desired distribution, but with some small amount of error. In this paper, we focus on the problem of exact distributed sampling. Our main contribution is to show that these distributed Markov chains in tandem with techniques from the sequential setting, namely coupling from the past and bounding chains, can be used to design $O(\log n)$-round LOCAL model exact sampling algorithms for a class of weighted local constraint satisfaction problems. This general result leads to $O(\log n)$-round exact sampling algorithms that use small messages (i.e., run in the CONGEST model) and polynomial-time local computation for some important special cases, such as sampling weighted independent sets (aka the hardcore model) and weighted dominating sets.