Shared Randomness and Parallel Rounds in Permutation Sampling
cs.IT, cs.DS, math.IT
Submitted: 2026-10-31
Updated: 2026-11-18
Terminology
Sources
- Entropic Independence I: Modified Log-Sobolev Inequalities for Fractionally Log-Concave Distributions and High-Temperature Ising Models
- MergeShuffle: A Very Fast, Parallel Random Permutation Algorithm
- Randomization Beyond Deterministic Adaptivity in Parallel Sampling
- Serial Depth of Adaptive Parallel Sampling: Lower Bounds and Schedules for Masked Diffusion Models
- KL Before and After Mixing: A Round-Complexity Separation in Parallel Sampling
- The Cost of Conservation: Coordination-Memory Laws for Exact-Support Generation
Related papers
- The Gaussian Multiuser Channel Capacity Region
- The mathematical landscape of partial information decomposition: A comprehensive review of properties and measures
- Electromagnetic Signal and Information Theory: A Continuous-Aperture Array Perspective
- Analytically Characterized Optimal Power Control for Signal-Level-Integrated Sensing, Computing and Communication in Federated Learning
- Information Spectrum Methods for Multiple-Access Channels--Part I: epsilon-Capacity Regions in the Mixed Gaussian Case
- Seed Recycling: Explicit Codes for Mixed Synchronization Errors Matching the Leading Term of the Gilbert--Varshamov Bound