Metraipolis › archive › dc_fe105d8932f7
Shared Randomness and Parallel Rounds in Permutation Sampling — arXiv:2611.01028
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.01028
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:38:37.760Z
- SHA-256 of the archived text
b09275b5aca5f62cf8d8d3fb2bef843ac53622c2438d8c15ad0477502eba0552- Stable URL of this page
https://metraipolis.com/documento/dc_fe105d8932f7
How to cite
Shared Randomness and Parallel Rounds in Permutation Sampling — arXiv:2611.01028 — arXiv (en), https://arxiv.org/abs/2611.01028 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fe105d8932f7 (Metraipolis archive dc_fe105d8932f7, sha256 b09275b5aca5f62cf8d8d3fb2bef843ac53622c2438d8c15ad0477502eba0552)
BibTeX
@misc{dcfe105d8932f7,
title = {Shared Randomness and Parallel Rounds in Permutation Sampling — arXiv:2611.01028},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.01028},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fe105d8932f7; sha256 b09275b5aca5f62cf8d8d3fb2bef843ac53622c2438d8c15ad0477502eba0552},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.01028. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the shared randomness needed to sample a uniform permutation in parallel output rounds. Coordinates committed in the same round are independent conditional on the complete history and the current shared choice. Previous outputs are public; local computation and private randomness are free. We charge each shared choice by the logarithm of its conditional support size and sum these costs along the worst execution path. At every fixed round density $\rho\in(0,1)$, the optimal limiting total-variation error under any $o(n)$ shared budget matches the conditional-marginal optimum, even with arbitrary local kernels and adaptive coordination. A fixed improvement requires linear cost. For exact sampling in $R=\Theta(n)$ rounds, the optimum is $n\Phi(R/n)+O(\log n)$, where $\Phi$ linearly interpolates $\Phi(1/q)=\log q$. A protocol attaining this rate uses an initial seed and at most one further binary shared choice. When $\lceil n/2\rceil\le R\le n$, the finite optimum is $\log\binom{2(n-R)}{n-R}$, attained by an initial seed alone. The approximate converse uses an entropy inequality for sparse injections to control overlap with the target. The exact construction reuses randomness retained in a shared label partition after the first-stage outputs are exposed.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.IT, nuovi lavori del giorno).
Categorie arXiv: Information Theory (cs.IT) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.01028 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:05:37.173Z dalla pagina https://arxiv.org/list/math.IT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).