AI & ML
Shared Randomness and Parallel Rounds in Permutation Sampling
arXiv math.IT0 views
arXiv:2611.01028v2 Announce Type: replace Abstract: Sampling a uniformly random permutation of $[n]$ in parallel is a coordination problem: $n$ processors, one per coordinate, must output distinct values. A single round requires a shared seed of $\log n!$ nats, while $n$ rounds require no shared randomness. We determine the tradeoff in between for $R$ rounds, in which the values of each round are written independently given the shared randomness and the earlier output, and the output must be a uniform permutation, exactly or within total-variation error $\varepsilon$. Shared randomness is measured by its support size or by its entropy, and it is either fixed in advance or drawn adaptively during the execution. For exact sampling, all four costs equal one explicit combinatorial quantity up to an absolute additive constant. A fixed error $0<\varepsilon<1$ shortens the seed by $O(1)$ nats in one round, where the least number of seed values, an approximate nonnegative tensor rank, is $(1-3\varepsilon/2)\,n!$ up to an additive two for $\varepsilon\le1/2$. The saving is $\Theta((\log n)^2)$ nats in two rounds, with a sharp constant, and of lower order for $R=o(n)$; for $R\sim\rho n$ with $0<\rho<1$ it is linear in $n$, with the optimal rate given by a variational formula. Here, errors above an explicit threshold need only $o(n)$ nats, and at every positive error below it, shared randomness drawn adaptively has strictly smaller entropy than a seed fixed in advance. A central tool is a change of measure that turns lower bounds with error into entropy bounds for a single batch of distinct, nearly independent values. The results for sublinearly and linearly many rounds extend to sampling without replacement.
Source:https://arxiv.org/abs/2611.01028PreviousOrbits as Strong Models: Kolmogorov Structure Function under SymmetryNextSIGMA: speaker-isolated, symptom-structured multimodal estimation of depression severity from clinical interviews
Related posts
How OpenAI’s Performance Factory keeps ChatGPT fast
0OpenAI Blog
Meta’s AI agent Muse is mixing up conversations and exposing private data, report says
0TechCrunch
Google gives Gemini the ability to use your Mac for you
0TechCrunch
Linkup /research is async. Treating it as synchronous is the bug, in code and in the freeze case
0dev.to
Fuck Your AI Safeguards
0Hacker News
Chrome AI features wasting much bandwidth
0Hacker News