Skip to content
DraconiticResearch
Search Sources API
190,860 studies31 sourcesUpdated 1 h ago
PreprintCC BY 4.0arXiv

A $π/ 4$ lower bound for random access in symmetric linear ensembles under optimal decoding

  • Daniella Bar-Lev
  • Ohad Elishco
  • Ryan Gabrys
Open at sourcePDFDOICite

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

  1. Structured Masked Diffusion for Shared-Codebook Unsourced Random Access Decoding
    Taekyun Lee, Jiyoung Yun, Jeffrey G. Andrews +1
    arXivPreprintCC BY 4.0Full textGeneral mathematicsarXiv
  2. Exact Joint MAP Decoding for Unknown Load and Message Counts in Orthogonal Unsourced Random Access
    Mohammad Kazemi, Mert Ozates
    arXivPreprintCC BY 4.0Full textGeneral mathematicsarXiv
  3. Optimal Average Success Probabilities of Binary (n,n−1) and (n,n−2) Quantum Random Access Codes
    Shuo Tan, Syed A. Jafar
    arXivPreprintCC BY 4.0Full textGeneral mathematicsQuantum physics & quantum informationarXiv
  4. Optimal random quantisers for spherically symmetric distributions
    Luc Pronzato, Anatoly A. Zhigljavsky
    HALPreprintCC BY 4.0Full textStatisticsHALarXiv
  5. Spectral properties of deterministic matrices multiplied by rotationally invariant random non-Hermitian ensembles
    Pierre Bousseyroux, Marc Potters
    arXivPreprintarXiv licenceFull textMathematical physicsProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{barlev2026lower,
  title = {{A $π/ 4$ lower bound for random access in symmetric linear ensembles under optimal decoding}},
  author = {Daniella Bar-Lev and Ohad Elishco and Ryan Gabrys},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.38446},
  eprint = {2610.38446},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.38446},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - A $π/ 4$ lower bound for random access in symmetric linear ensembles under optimal decoding
AU  - Daniella Bar-Lev
AU  - Ohad Elishco
AU  - Ryan Gabrys
PY  - 2026
DA  - 2026/10/28
PB  - arXiv
DO  - 10.48550/arxiv.2610.38446
UR  - https://arxiv.org/abs/2610.38446
AB  - 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.
ER  -