arXiv preprint ·
Shared Randomness and Parallel Rounds in Permutation Sampling
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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 $ρ\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=Θ(n)$ rounds, the optimum is $nΦ(R/n)+O(\log n)$, where $Φ$ linearly interpolates $Φ(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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Information Theory
Equal Hamming Weights at Fixed Root Order and Applications to Constacyclic MDS Codes
Polynomial-Time Minimax Prediction for Stationary Renewal Processes
Cyclotomic polynomials with trinomial irreducible factors over finite fields
Secrecy Sum-Rate Maximization for RSMA-Enabled Pinching-Antenna Systems
Spatial Token Interleaving and Two-Pass BP Decoding for Semantic Image Transmission
Get the few papers worth your time in Information Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.