Metraipolis › archive › dc_617af2401908
A Universal Threshold Theory for Local Properties of Random Linear Codes — arXiv:2611.07661
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.07661
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-06T14:52:56.186Z
- SHA-256 of the archived text
889c4470cc8d2a40de7c19f8e2c63802e2921b7d5e2aae29bd9f7aed63fd1eb7- Stable URL of this page
https://metraipolis.com/documento/dc_617af2401908
How to cite
A Universal Threshold Theory for Local Properties of Random Linear Codes — arXiv:2611.07661 — arXiv (en), https://arxiv.org/abs/2611.07661 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_617af2401908 (Metraipolis archive dc_617af2401908, sha256 889c4470cc8d2a40de7c19f8e2c63802e2921b7d5e2aae29bd9f7aed63fd1eb7)
BibTeX
@misc{dc617af2401908,
title = {A Universal Threshold Theory for Local Properties of Random Linear Codes — arXiv:2611.07661},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.07661},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_617af2401908; sha256 889c4470cc8d2a40de7c19f8e2c63802e2921b7d5e2aae29bd9f7aed63fd1eb7},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.07661. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Thresholds for local properties tell us which guarantees to expect from random linear codes (RLCs) and help us carry those guarantees over to structured codes. A monotone property is $b$-local if a collection of at most $b$ codewords can witness its satisfaction or failure, as in list decoding and list recovery. The threshold of $\mathcal P$ is the code dimension at which the probability that an RLC in $\mathbb{F}_q^n$ satisfies $\mathcal P$ crosses $1/2$ in a sharp transition. We show that the threshold of a $b$-local property $\mathcal P$ is within $O(b)$ dimensions of the expectation threshold. This is the dimension predicted by the best union bound over covers of $\mathcal P$: families of subspaces such that the span of every witness contains at least one member. This gives a general derandomization statement: Any decreasing local property satisfied by RLCs at a given rate holds at a similar rate for pseudorandom ensembles that fool the cover union bound. In addition to previously studied ensembles, these include codes whose parity-check matrix is sampled from a small-bias distribution. Because our threshold characterization applies to all local properties, this derandomization also reaches properties beyond the scope of earlier reductions, including maximum loads in linear hashing for arbitrary input sets, rank-metric list decoding, and list decoding from insertion-deletion errors and burst errors. Our theorem unifies and strengthens prior works on row-symmetric and coordinate-wise linear characterizations, which located the threshold to within $O(q^{2b}\log_q n)$ and $O(b^2+nb/\log_2 q)$ dimensions, respectively. We obtain $O(b)$ error for every $b$-local property, independently of alphabet size. Under suitable pseudorandomness bounds, the rate loss vanishes for every $b=o(n)$, compared to $b=O(\log n)$ for earlier frameworks.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Information Theory (cs.IT) ; Computational Complexity (cs.CC); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2611.07661 — 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-06T14:24:27.852Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).