Fast Spanning Tree Sampling in Broadcast Congested Clique
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917362404425728 |
|---|---|
| author | Anari, Nima Haqi, Alireza |
| author_facet | Anari, Nima Haqi, Alireza |
| contents | We present the first polylogarithmic-round algorithm for sampling a random spanning tree in the (Broadcast) Congested Clique model. For any constant $c > 0$, our algorithm outputs a sample from a distribution whose total variation distance from the uniform spanning tree distribution is at most $O(n^{-c})$ in at most $c \cdot \log^{O(1)}(n)$ rounds. The exponent hidden in $\log^{O(1)}(n)$ is an absolute constant independent of $c$ and $n$. This is an exponential improvement over the previous best algorithm of Pemmaraju, Roy, and Sobel (PODC 2025) for the Congested Clique model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_25018 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Fast Spanning Tree Sampling in Broadcast Congested Clique Anari, Nima Haqi, Alireza Data Structures and Algorithms Distributed, Parallel, and Cluster Computing We present the first polylogarithmic-round algorithm for sampling a random spanning tree in the (Broadcast) Congested Clique model. For any constant $c > 0$, our algorithm outputs a sample from a distribution whose total variation distance from the uniform spanning tree distribution is at most $O(n^{-c})$ in at most $c \cdot \log^{O(1)}(n)$ rounds. The exponent hidden in $\log^{O(1)}(n)$ is an absolute constant independent of $c$ and $n$. This is an exponential improvement over the previous best algorithm of Pemmaraju, Roy, and Sobel (PODC 2025) for the Congested Clique model. |
| title | Fast Spanning Tree Sampling in Broadcast Congested Clique |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2603.25018 |