Metraipolis › archive › dc_b279e239012b
A $π/ 4$ lower bound for random access in symmetric linear ensembles under optimal decoding — arXiv:2610.38446
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.38446
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-01T02:39:40.607Z
- SHA-256 of the archived text
281a13ae391dc2bd1dbbd774a9c9b90af4b60924df45fc70a3956b0b2fe2bb58- Stable URL of this page
https://metraipolis.com/documento/dc_b279e239012b
How to cite
A $π/ 4$ lower bound for random access in symmetric linear ensembles under optimal decoding — arXiv:2610.38446 — arXiv (en), https://arxiv.org/abs/2610.38446 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b279e239012b (Metraipolis archive dc_b279e239012b, sha256 281a13ae391dc2bd1dbbd774a9c9b90af4b60924df45fc70a3956b0b2fe2bb58)
BibTeX
@misc{dcb279e239012b,
title = {A $π/ 4$ lower bound for random access in symmetric linear ensembles under optimal decoding — arXiv:2610.38446},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.38446},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b279e239012b; sha256 281a13ae391dc2bd1dbbd774a9c9b90af4b60924df45fc70a3956b0b2fe2bb58},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.38446. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\pi/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. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.IT, nuovi lavori del giorno). Categorie arXiv: Information Theory (cs.IT). Pagina del lavoro: https://arxiv.org/abs/2610.38446 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-01T02:15:43.722Z dalla pagina https://arxiv.org/list/math.IT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).