Algebraic Expander Codes

Swastik Kopparty, Itzhak Tamo · 2026 · arXiv

| 编号 QE057 | 主题 经典编码基础 | 链接 arXiv:2603.24788 |

摘要

摘要保留原文（英文）

摘要取自 arXiv / 出版方元数据，未作翻译，以保证与原文一致。

Expander (Tanner) codes combine sparse graphs with local constraints, enabling linear-time decoding and asymptotically good distance-rate tradeoffs. A standard constraint-counting argument yields the global-rate lower bound R >= 2r-1 for a Tanner code with local rate r, which gives no positive-rate guarantee in the low-rate regime r <= 1/2. We introduce Algebraic Expander Codes, an explicit algebraic family of Tanner-type codes whose local constraints are Reed-Solomon and whose global rate remains bounded away from 0 for every fixed r in (0,1), while achieving constant relative distance. Our codes are defined by evaluating a structured subspace of polynomials on an orbit of a non-commutative subgroup of AGL(1,F) generated by translations and scalings. The resulting sparse coset geometry forms a strong spectral expander, proved via additive character-sum estimates, while the rate analysis uses a new notion of polynomial degree and a polytope-volume/dimension-counting argument.

本站词条在引用该文献时，会以 wikilink（sources/QE057）链接到本页；右侧「反向链接」面板自动列出所有引用它的词条。