Efficient subspace design codes with smaller alphabets and fast encoding
Efficient construction of subspace design codes over constant alphabet
Information Theory
Summary
Coding theory helps fix errors in data sent over noisy channels, but often needs big alphabets that are tough to handle. The authors improved on a previous breakthrough by making these special error-correcting codes work with smaller alphabets that grow more slowly as code complexity rises. They also created a more efficient way to encode data using algebraic geometry methods, which speeds up the process. This work advances the practical use of powerful error-correcting codes by reducing the size of the symbols and the time needed to process them.
What this means in practice
- •For communication engineers: Improve error-correcting hardware by using codes with smaller alphabets and faster encoding to enhance efficiency and reduce resource needs in data transmission.
- •For storage system designers: Design storage solutions that implement efficient subspace-design codes to better handle errors without increasing the alphabet size excessively, enabling more compact storage devices.
Authors
Shu Liu
Abstract
Subspace-design codes form a central unifying framework in coding theory, connecting probabilistic existence results and explicit algebraically structured constructions. The two core families are folded Reed-Solomon codes and univariate multiplicity codes, both possessing the subspace-design property. These codes reach list-decoding capacity with polynomial-size lists, but their alphabet size grows with code length and hurts practical efficiency. Goyal, Guruswami, and Hsieh achieved a major breakthrough: they constructed the first explicit subspace-design codes over constant-size alphabets via the Alon-Edmonds-Luby expander framework, settling an open problem and showing subspace-design properties can hold without large alphabets. Despite recent progress, constructing subspace-design codes with low-complexity efficient encoding remains a critical open challenge. This work gives an explicit construction of r-dimensional subspace-design codes over a constant alphabet whose size grows exponentially with r. By comparison, Goyal et al. (FOCS 2026) built r-dimensional subspace-design codes with alphabet size doubly exponential in r squared. Our construction is computationally efficient: encoding scales quadratically with block length and linearly with dimension r in field operations. We use modified algebraic geometry codes, replacing rational evaluation points with higher-degree places to obtain a valid additive code. To confirm parameter bounds, we use Moore matrices to analyze determinants with many zero entries. We also generalize univariate multiplicity codes, originally built from Reed-Solomon codes, to algebraic geometry codes, and prove these AG-multiplicity codes achieve optimal parameters.