Explicit Constant-Alphabet Subspace Design Codes

Jun-Ting Hsieh; Rohan Goyal; Venkatesan Guruswami

arxiv: 2604.15218 · v1 · submitted 2026-04-16 · 💻 cs.IT · cs.CC· math.IT

Explicit Constant-Alphabet Subspace Design Codes

Rohan Goyal , Venkatesan Guruswami , Jun-Ting Hsieh This is my paper

Pith reviewed 2026-05-10 09:51 UTC · model grok-4.3

classification 💻 cs.IT cs.CCmath.IT

keywords subspace design codesconstant alphabetexplicit constructionsAEL frameworklist recoveryexpander codeslocal properties

0 comments

The pith

Explicit constructions yield subspace design codes with constant-sized alphabets.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper constructs explicit subspace design codes where the alphabet size stays constant as the block length grows. The subspace design property ensures the code performs like random linear codes on every local property. Earlier explicit codes required alphabet size to grow polynomially with length. The construction applies the expander-based Alon-Edmonds-Luby framework using expanders and algebraic base codes to achieve this. It also improves parameters for list-recovery tasks.

Core claim

The authors provide explicit constructions of subspace design codes over constant-sized alphabets using the expander-based Alon-Edmonds-Luby (AEL) framework. This answers the open question about such constructions and obtains the local properties consequence in a unified way through the subspace design property.

What carries the argument

The Alon-Edmonds-Luby (AEL) framework instantiated with algebraic base codes and suitable expanders, which preserves the subspace design property at constant alphabet size.

If this is right

The constructed codes have performance similar to random linear codes with respect to all local properties.
Explicit constant-alphabet subspace design codes are now available.
Parameters for list-recovery see some improvements.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

This method could be applied to construct explicit codes with other desirable combinatorial properties.
May lead to better derandomized constructions in related areas of coding theory.
Opens the door for constant-alphabet codes in applications requiring subspace designs like in locally testable codes.

Load-bearing premise

The AEL framework, when combined with the right algebraic base codes and expanders, keeps the subspace design property intact while maintaining a constant alphabet size.

What would settle it

Verify whether the AEL construction on chosen parameters produces a code whose alphabet size remains constant independent of block length and satisfies the subspace design condition.

read the original abstract

The subspace design property for additive codes is a higher-dimensional generalization of the minimum distance property. As shown recently by Brakensiek, Chen, Dhar and Zhang, it implies that the code has similar performance as random linear codes with respect to all "local properties". Explicit algebraic codes, such as folded Reed-Solomon and multiplicity codes, are known to have the subspace design property, but they need alphabet sizes that grow as a large polynomial in the block length. Constructing explicit constant-alphabet subspace design codes was subsequently posed as an open question in Brakensiek, Chen, Dhar and Zhang. In this work, we answer their question and give explicit constructions of subspace design codes over constant-sized alphabets, using the expander-based Alon-Edmonds-Luby (AEL) framework. This generalizes the recent work of Jeronimo and Shagrithaya, which showed that such codes share local properties of random linear codes. Our work obtains this consequence in a unified manner via the subspace design property. In addition, our approach yields some improvements in parameters for list-recovery.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives the first explicit constant-alphabet subspace design codes by lifting algebraic base codes with AEL, settling the Brakensiek et al. question while unifying local properties.

read the letter

The main takeaway is that this work supplies explicit subspace design codes over constant alphabets. That directly answers the open question from Brakensiek, Chen, Dhar and Zhang, who showed the property implies random-linear-like behavior on all local properties but left constant-alphabet constructions open. The authors apply the AEL expander lifting to base codes such as folded Reed-Solomon that already possess the design property, and they claim the output retains enough of it while the alphabet stays fixed. They also generalize the Jeronimo-Shagrithaya result and obtain modest gains on list-recovery parameters in some ranges. The approach is straightforward and reuses existing explicit ingredients, which keeps the construction concrete rather than existential. The unification through the design property is cleaner than proving each local property separately. The soft spot is the parameter regime. The AEL step must compose the subspace intersection bounds without forcing the alphabet or the design strength to degrade, and this depends on the precise expander degree and how the lifting interacts with the base code parameters. The abstract asserts the right choices exist, but the calculations need to be checked line by line to confirm the constants remain independent of block length. If those numbers hold, the result is fine; if they slip, the claim would need adjustment. This paper is aimed at researchers in explicit coding theory and derandomization who care about codes matching random linear behavior on local tests. A reader already familiar with AEL and subspace designs will extract the most value. It deserves a serious referee because it hits a stated open question with an explicit construction rather than another existence argument.

Referee Report

1 major / 3 minor

Summary. The manuscript claims to resolve the open question of Brakensiek, Chen, Dhar and Zhang by providing explicit constructions of subspace design codes over constant-sized alphabets. It applies the expander-based Alon-Edmonds-Luby (AEL) framework to algebraic base codes (such as folded Reed-Solomon codes) that already possess the subspace design property, showing that the resulting codes retain a sufficiently strong subspace design property while the alphabet size remains constant (independent of block length). The work also unifies prior results on local properties of such codes and reports improvements in list-recovery parameters.

Significance. If the parameter regime is verified, the result is significant: it supplies the first explicit constant-alphabet codes with the subspace design property, implying that these codes match the local-property performance of random linear codes. The approach is constructive, leverages the established AEL framework, and provides a unified treatment via the subspace design property rather than case-by-case arguments. Credit is due for the explicitness and for generalizing the recent Jeronimo-Shagrithaya work on local properties.

major comments (1)

[Section describing the AEL instantiation and parameter selection (likely §4)] The central claim that the AEL transformation preserves the subspace design property while keeping the output alphabet size constant depends on the specific composition of intersection bounds, expander degree, and base-code parameters. The manuscript invokes existence results for expanders from prior literature but does not appear to contain an explicit calculation or bound demonstrating that the alphabet size remains bounded by a constant (rather than growing with block length or polylogarithmically) for the target design parameters. This calculation is load-bearing for answering the open question.

minor comments (3)

[Abstract] The abstract states that the approach 'yields some improvements in parameters for list-recovery' but does not quantify the improvement relative to the parameters in Jeronimo-Shagrithaya or Brakensiek et al.
[Preliminaries and main construction sections] Notation for the subspace design parameters (e.g., the intersection bound t and the dimension k) should be introduced once in the preliminaries and used consistently; several later sections appear to reuse symbols without redefinition.
[Introduction or conclusion] The paper would benefit from a short table comparing the new constant-alphabet parameters (rate, alphabet size, design strength) against the polynomial-alphabet constructions of Brakensiek et al. and the local-property results of Jeronimo-Shagrithaya.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment of our work and for identifying the need for greater explicitness in the parameter analysis. We address the major comment below and will revise the manuscript accordingly.

read point-by-point responses

Referee: [Section describing the AEL instantiation and parameter selection (likely §4)] The central claim that the AEL transformation preserves the subspace design property while keeping the output alphabet size constant depends on the specific composition of intersection bounds, expander degree, and base-code parameters. The manuscript invokes existence results for expanders from prior literature but does not appear to contain an explicit calculation or bound demonstrating that the alphabet size remains bounded by a constant (rather than growing with block length or polylogarithmically) for the target design parameters. This calculation is load-bearing for answering the open question.

Authors: We agree that an explicit, self-contained calculation of the parameter regime is necessary to make the constancy of the alphabet size fully transparent. While the manuscript already selects the expander degree d as a sufficiently large constant (depending only on the target subspace design parameters and the base-code intersection bounds) and invokes the existence of (d,λ)-expanders for constant d and λ, we will add a dedicated parameter-verification subsection in the revised §4. This subsection will derive the required lower bound on d explicitly from the composition of the AEL intersection lemma with the base-code subspace design property, confirming that the output alphabet size is bounded by a constant independent of block length (depending only on the design parameters ε, δ, and the base-code rate). The revised text will also include a short table summarizing the chosen constants for the main parameter regimes. revision: yes

Circularity Check

0 steps flagged

No significant circularity; construction is self-contained via external framework

full rationale

The paper's derivation applies the established AEL framework (Alon-Edmonds-Luby) to known algebraic base codes possessing the subspace design property (e.g., folded Reed-Solomon from prior literature by Brakensiek et al.). The central claim of constant-alphabet explicit codes follows from composing the subspace design parameters under the AEL lifting and invoking external expander existence results, without any self-definitional reduction, fitted inputs renamed as predictions, or load-bearing self-citations. The generalization of Jeronimo-Shagrithaya is presented as an application rather than a foundational assumption, and all key steps (preservation of design property, alphabet size independence) are derived from the cited framework's properties rather than assumed circularly in the inputs. This is a standard non-circular explicit construction paper.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The construction rests on the existence of suitable expander graphs and the preservation properties of the AEL framework, both taken from prior literature; no new free parameters or invented entities are introduced in the abstract.

axioms (1)

domain assumption Existence of expander graphs with the expansion and degree parameters required by the AEL instantiation
The AEL framework requires good expanders whose parameters must be chosen to keep the alphabet constant while preserving subspace design.

pith-pipeline@v0.9.0 · 5493 in / 1243 out tokens · 29529 ms · 2026-05-10T09:51:44.595578+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

2 extracted references · 2 canonical work pages

[1]

Probabilistic checking of proofs: A new characterization of NP.Journal of the ACM (JACM), 45(1):70–122, 1998

13 [AS98] Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP.Journal of the ACM (JACM), 45(1):70–122, 1998. 4 [BCDZ25a] Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang. Combinatorial bounds for list recovery via discrete Brascamp–Lieb inequalities.arXiv preprint arXiv:2510.13775,

work page arXiv 1998
[2]

arXiv preprint arXiv:2510.13777 , year=

To appear in STOC 2026. 8, 9, 10, 11, 12 [BCDZ25b] Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang. From Random to Explicit via Subspace Designs With Applications to Local Properties and Matroids.arXiv preprint arXiv:2510.13777, 2025. To appear in STOC 2026. 1, 3, 4, 5, 6, 8, 9, 10, 11 [BGM24] JoshuaBrakensiek, SivakanthGopi, andVisuMakam. Gen...

work page arXiv 2026

[1] [1]

Probabilistic checking of proofs: A new characterization of NP.Journal of the ACM (JACM), 45(1):70–122, 1998

13 [AS98] Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP.Journal of the ACM (JACM), 45(1):70–122, 1998. 4 [BCDZ25a] Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang. Combinatorial bounds for list recovery via discrete Brascamp–Lieb inequalities.arXiv preprint arXiv:2510.13775,

work page arXiv 1998

[2] [2]

arXiv preprint arXiv:2510.13777 , year=

To appear in STOC 2026. 8, 9, 10, 11, 12 [BCDZ25b] Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang. From Random to Explicit via Subspace Designs With Applications to Local Properties and Matroids.arXiv preprint arXiv:2510.13777, 2025. To appear in STOC 2026. 1, 3, 4, 5, 6, 8, 9, 10, 11 [BGM24] JoshuaBrakensiek, SivakanthGopi, andVisuMakam. Gen...

work page arXiv 2026