Algebraic Expander Codes

Swastik Kopparty, Itzhak Tamo · 2026

Read Algebraic Expander Codes by Swastik Kopparty, Itzhak Tamo (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-24788.txt.

Introduction

Kopparty and Tamo introduce algebraic expander codes, Tanner-type codes with Reed-Solomon local constraints. Standard counting gives no positive-rate guarantee when the local rate is at most half. That low-rate regime matters for applications needing algebraic locality. Their codes evaluate a polynomial subspace on an orbit of a subgroup of affine maps. The coset geometry forms a strong spectral expander, proved with character sums. The global rate stays bounded away from zero, with constant relative distance.

Catalog record

CREATORSwastik Kopparty, Itzhak Tamo
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE79886
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.24788

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Algebraic Expander Codes Swastik Kopparty, Itzhak Tamo Abstract 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 ≥ 2 ​ r − 1 R\geq 2r-1 for a Tanner code with local rate r r , which gives no positive-rate guarantee in the low-rate regime r ≤ 1 / 2 r\leq 1/2 . This regime is nonetheless important in applications that require algebraic local constraints (e.g., Reed–Solomon locality and the Schur-product/multiplication property). 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 0 for every fixed r ∈ ( 0 , 1 ) r\in(0,1) (in particular, for r ≤ 1 / 2 r\leq 1/2 ), 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 , 𝔽 ) \mathrm{AGL}(1,\mathbb{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. 1 Introduction Expander codes, introduced by Sipser and Spielman [ 12 ] , instantiate the Tanner-code viewpoint [ 14 ] : a long code is specified by local constraints placed on a sparse graph. When the underlying graph has strong expansion, this yields asymptotically good codes with efficient decoding algorithms (see, e.g., [ 12 , 15 , 9 ] ). A central challenge in the design of expander codes is the inherent tension between the rate of the local code and the guaranteed rate of the global code. For an expander code defined on a regular graph with local codes of rate r , the standard constraint-counting argument yields the lower bound on the global rate R\geq 2r-1 [ 14 ] . This bound implies a sharp threshold: to guarantee a positive global rate via this argument, the local codes must have rate r>1/2 . In the “low-rate regime” where r\leq 1/2 , the bound 2r-1 becomes non-positive. This does not preclude positive-rate constructions, but it removes the standard black-box guarantee. Despite this barrier, the regime of r\leq 1/2 is of theoretical and practical interest, particularly when the local codes possess specific algebraic structures. A primary motivation stems from the multiplication property of Reed–Solomon (RS) codes. If \mathcal{C} is an RS code of rate r , the component-wise product (Schur product) of two codewords belongs to an RS code of rate approximately 2r . This follows because the product of two polynomials of degree less than k has degree less than 2k-1 , and evaluation commutes with multiplication [ 11 ] . For the product code to be a non-trivial error-correcting code (i.e., rate strictly less than 1 ), the initial code must satisfy r<1/2 . This multiplication property is important in applications such as fault-tolerant quantum computing and High-Dimensional Expanders (HDX). For example, recent constructions of Quantum LDPC codes with transversal non-Clifford gates by Golowich and Lin [ 7 ] rely heavily on products of algebraic codes with rates below half. Similarly, Dinur, Liu, and Zhang [ 6 ] highlight the importance of constructing codes with the multiplication property, and construct high-dimensional expanders with this property. Thus, there is a compelling need for explicit expander codes that maintain the structure of low-rate Reed–Solomon local constraints while achieving a non-trivial global rate. In this work, we resolve these challenges. We present an explicit construction of expander codes that achieve a positive global rate for any fixed local rate r\in(0,1) , and specifically in the challenging regime of r\leq 1/2 . Crucially, our construction ensures that the local constraints are Reed–Solomon codes. This allows our codes to support the multiplication property required for the aforementioned applications while simultaneously achieving linear minimum distance via spectral expansion [ 4 ] . Main theorem (informal). Fix any constant local rate r\in(0,1) . For infinitely many block lengths n we give an explicit linear code \mathcal{C}\subseteq\mathbb{F}^{n} such that: (i) every coordinate participates in two local Reed–Solomon constraints of asymptotic rate at most r ; (ii) \mathcal{C} has constant rate and linear (constant relative) distance; and (iii) the underlying bipartite coset graph is a strong spectral expander (quantified by an explicit second singular value bound). What is new. Unlike the standard “graph + local code” paradigm (where one chooses a d -regular expanding graph and a length- d local code independently and then glues them together via a Tanner construction), our approach is purely algebraic. We define a single orbit-evaluation code, and the Tanner/expander graph arises as an emergent coset geometry coming from the action of two subgroups. We term these codes Algebraic Expander Codes to emphasize this distinction. A second key point is that the two subgroups are of opposing algebraic types , translations and scalings. Their non-commutative interaction yields a sparse underlying geometry (in contrast with the dense, grid-like geometries that arise from commuting subgroups) while still admitting strong spectral expansion. 1.1 Connection to Locally Recoverable Codes and Graph Density Our construction builds upon the algebraic framework of Locally Recoverable Codes (LRCs) established by the second author and Barg [ 13 ] . In that framework, a code is defined by evaluating a special subspace of polynomials over some orbits of a subgroup G of the affine group \mathrm{AGL}(1,\mathbb{F}) . The special subspace of polynomials guarantees that the restriction of any codeword to an orbit of G corresponds to a univariate polynomial of bounded degree, ensuring the local view is an RS code. In [ 13 ] , this algebraic framework was extended to construct codes with multiple recovering sets, where each coordinate participates in multiple (typically two) local codes. To achieve this, the evaluation set is partitioned into orbits under the action of two distinct subgroups of \mathrm{AGL}(1,\mathbb{F}) , denoted as G and H . However, the constructions in [ 13 ] were restricted to subgroups of the same algebraic type , either two additive subgroups representing translations in distinct directions, or two multiplicative subgroups representing two different scalings. We note that this approach had two primary limitations. First, it did not support arbitrary local rates, requiring r>1/2 to ensure a non-trivial rate, which mirrors the bounds of standard expander codes. Second, and more critically, using subgroups of the same type imposes inherent structural limitations on the code’s underlying graph, which we explain next. These codes admit a natural bipartite graph representation: code coordinates correspond to edges, while local codes (the orbits of G or H ) correspond to vertices. Specifically, an edge connects the unique G -orbit and H -orbit containing that coordinate. The degree of any vertex is simply the size of its corresponding orbit. When G and H share the same algebraic type, they necessarily commute. Consequently, the resulting structure is a complete bipartite graph. While such graphs are excellent spectral expanders, their maximal degree scales linearly with the number of vertices. This contrasts with the typical objective of expander code constructions of achieving sublinear, and ideally constant, degrees. The limitation arises because commutative

Read the complete text