A pi / 4 lower bound for random access in symmetric linear ensembles under optimal decoding
cs.IT, math.IT
Submitted: 2026-10-28
Updated: 2026-10-28
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study the expected number of random linear observations required to recover a prescribed information symbol.
Abstract
We study the expected number of random linear observations required to recover a prescribed information symbol. For ensembles with uniformly random supports, independently sampled nonzero coefficients, and uniformly bounded column weights, we prove that the asymptotic normalized expected recovery time is at least π/4 under optimal decoding. The result holds over finite or infinite fields and extends the lower bound previously established for binary fully symmetric codes under peeling decoding. For singleton - pair observations, we determine the exact limiting expectation and show that optimal and peeling decoding have the same limit, independently of the field and coefficient distribution. The minimum within this family is approximately 0.793933445, which explicit constructions attain asymptotically over every fixed finite field.
Related papers
- The Gaussian Multiuser Channel Capacity Region
- The mathematical landscape of partial information decomposition: A comprehensive review of properties and measures
- 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
- Second-Order Image Characterization with Distortion and Secrecy