Explicit Almost-Optimal $\varepsilon$-Balanced Codes via Free Expander Walks

Jun-Ting Hsieh; Rachel Yun Zhang; Sidhanth Mohanty

arxiv: 2601.12606 · v2 · submitted 2026-01-18 · 💻 cs.CC · cs.DM· cs.DS· math.CO

Explicit Almost-Optimal varepsilon-Balanced Codes via Free Expander Walks

Jun-Ting Hsieh , Sidhanth Mohanty , Rachel Yun Zhang This is my paper

Pith reviewed 2026-05-16 13:26 UTC · model grok-4.3

classification 💻 cs.CC cs.DMcs.DSmath.CO

keywords explicit codesexpander walksGilbert-Varshamov boundnear-X-Ramanujan graphsbalanced codesbias amplification

0 comments

The pith

Free expander walks on near-X-Ramanujan graphs produce explicit codes with almost-optimal rate for distance (1-ε)/2.

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

The paper constructs explicit families of codes whose rate and distance nearly match the Gilbert-Varshamov bound in the low-rate regime. It replaces the s-wide-replacement product from Ta-Shma's 2017 construction with ordinary expander walks that take each step on a distinct expander drawn from a fixed sequence of near-X-Ramanujan graphs. This yields the same rate bound Ω(ε^{2+o(1)}) while simplifying the underlying graph product. A reader would care because explicit constructions with these parameters are building blocks for efficient error-correcting codes and derandomization procedures.

Core claim

We obtain an explicit family of ε-balanced codes with relative distance (1-ε)/2 and rate Ω(ε^{2+o(1)}) by performing ordinary expander walks on a carefully chosen sequence of distinct expanders derived from the near-X-Ramanujan graphs of O'Donnell and Wu; the same parameters are achieved as in Ta-Shma's construction but via a simpler mechanism.

What carries the argument

Free expander walks: ordinary expander walks in which each successive step uses a distinct expander taken from a sequence derived from near-X-Ramanujan graphs; this sequence supplies the bias amplification needed to reach the target distance.

If this is right

The construction yields explicit ε-balanced codes matching Ta-Shma's rate bound while avoiding the s-wide-replacement product.
The same sequence of near-X-Ramanujan graphs also supplies on-average lossless expanders and rotating expanders as immediate corollaries.
The approach isolates the role of the expander sequence, making the bias-amplification step modular.

Where Pith is reading between the lines

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

If the free-walk construction extends without hidden losses to other expander families, it could simplify analyses in related derandomization settings that rely on iterative bias reduction.
The modularity may allow substitution of future improved near-Ramanujan graphs to tighten the o(1) term in the rate exponent.

Load-bearing premise

The fixed sequence of near-X-Ramanujan graphs can be ordered so that the free expander walk amplifies bias to the claimed degree without incurring extra losses beyond those already present in the individual graphs.

What would settle it

An explicit calculation or small-instance simulation showing that the bias after k steps of the free walk falls short of the amplification factor required to reach distance (1-ε)/2 by more than an ε^{o(1)} multiplicative loss would falsify the central claim.

read the original abstract

We study the problem of constructing explicit codes whose rate and distance match the Gilbert-Varshamov bound in the low-rate, high-distance regime. In 2017, Ta-Shma gave an explicit family of codes where every pair of codewords has relative distance $\frac{1-\varepsilon}{2}$, with rate $\Omega(\varepsilon^{2+o(1)})$, matching the Gilbert-Varshamov bound up to a factor of $\varepsilon^{o(1)}$. Ta-Shma's construction was based on starting with a good code and amplifying its bias with walks arising from the $s$-wide-replacement product. In this work, we give a simpler almost-optimal construction, based on what we call free expander walks: ordinary expander walks where each step is taken on a distinct expander from a carefully chosen sequence. This sequence of expanders is derived from the construction of near-$X$-Ramanujan graphs due to O'Donnell and Wu. We additionally discuss some additional applications of near-$X$-Ramanujan graphs to "on average" lossless expansion and rotating expanders.

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

This paper gives a simpler explicit construction for almost-GV codes by using free walks on a sequence of O'Donnell-Wu near-X-Ramanujan graphs instead of Ta-Shma's s-wide replacement.

read the letter

The main advance here is a cleaner way to get rate Ω(ε^{2+o(1)}) codes with relative distance (1-ε)/2. The authors replace the wide-replacement product with ordinary walks where each step uses a fresh expander from the O'Donnell-Wu sequence. That change looks like a genuine simplification on the surface, and the abstract claims the same asymptotic parameters as Ta-Shma 2017 without the extra machinery. They also sketch a couple of side applications to average-case lossless expansion and rotating expanders, which are worth noting if those directions are active in your group. The construction itself appears to rest on solid prior work: the near-X-Ramanujan graphs are treated as a black box, which is fine if the eigenvalue bounds compose cleanly under the free-walk analysis. The paper does not seem to introduce new fitted parameters or circular reductions, so the central claim is at least stated in a falsifiable way. The soft spot is whether the bias-amplification analysis survives the switch to distinct graphs without picking up an extra ε^δ loss. The stress-test note flags exactly this point, and the abstract does not show the second-moment or Fourier calculation under the precise degree sequence, so a referee will need to see that derivation in full. If it holds without hidden factors, the result is a useful alternative technique. If it slips, the o(1) term could degrade. This is the kind of paper that belongs in a coding-theory or pseudorandomness reading group: technical but not opaque, and it directly engages the open question of explicit GV-matching codes. I would send it to peer review; the construction is concrete enough and the prior results are strong enough that the details are worth checking rather than desk-rejecting.

Referee Report

2 major / 2 minor

Summary. The manuscript presents a simpler explicit construction for almost-optimal ε-balanced codes achieving rate Ω(ε^{2+o(1)}) and relative distance (1-ε)/2, matching the Gilbert-Varshamov bound up to an ε^{o(1)} factor. The approach uses free expander walks on a sequence of distinct near-X-Ramanujan graphs derived from O'Donnell and Wu, replacing Ta-Shma's s-wide-replacement product, and discusses applications to on-average lossless expansion and rotating expanders.

Significance. If the free-walk bias amplification analysis holds without additional losses, the result simplifies an important explicit coding construction from Ta-Shma and introduces a reusable primitive for derandomization in coding theory and expanders.

major comments (2)

[§3.2] §3.2: The bias amplification analysis for free expander walks assumes eigenvalue bounds from the O'Donnell-Wu sequence compose without extra multiplicative factors, but no explicit second-moment or Fourier calculation is provided for the non-repeated graph setting; this is load-bearing for preserving the o(1) term in the rate Ω(ε^{2+o(1)}).
[Theorem 1.1] Theorem 1.1: The claimed rate relies on the sequence of near-X-Ramanujan graphs producing the same bias amplification as Ta-Shma without hidden ε^δ losses, yet the paper invokes the graphs as a black box without re-deriving the parameters under the free-walk definition.

minor comments (2)

[Definition 2.3] The notation for the sequence of expanders in Definition 2.3 could be clarified with an explicit example of the first few graphs.
Figure 2 caption omits the walk length parameter used in the plotted bias.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thoughtful review and valuable feedback on our manuscript. We appreciate the recognition of the simplification our free expander walks approach offers compared to Ta-Shma's construction. Below, we address the major comments point by point, and we plan to incorporate revisions to strengthen the presentation of the analysis.

read point-by-point responses

Referee: [§3.2] §3.2: The bias amplification analysis for free expander walks assumes eigenvalue bounds from the O'Donnell-Wu sequence compose without extra multiplicative factors, but no explicit second-moment or Fourier calculation is provided for the non-repeated graph setting; this is load-bearing for preserving the o(1) term in the rate Ω(ε^{2+o(1)}).

Authors: We agree that the current manuscript would benefit from a more explicit derivation of the bias amplification for the free expander walk setting. In the revised version, we will add a detailed second-moment calculation in §3.2 demonstrating that the eigenvalue bounds from the O'Donnell-Wu sequence compose multiplicatively without additional factors beyond those already accounted for in the o(1) term. This will confirm that the rate remains Ω(ε^{2+o(1)}). revision: yes
Referee: [Theorem 1.1] Theorem 1.1: The claimed rate relies on the sequence of near-X-Ramanujan graphs producing the same bias amplification as Ta-Shma without hidden ε^δ losses, yet the paper invokes the graphs as a black box without re-deriving the parameters under the free-walk definition.

Authors: We acknowledge that treating the O'Donnell-Wu graphs as a black box may obscure the parameter derivation. In the revision, we will include a self-contained re-derivation of the bias amplification parameters specifically for the free-walk model, showing that no hidden ε^δ losses are introduced and that the amplification matches Ta-Shma's up to the desired o(1) factors. This will be added as an appendix or expanded subsection supporting Theorem 1.1. revision: yes

Circularity Check

0 steps flagged

No circularity; construction uses external black-box graphs

full rationale

The paper introduces free expander walks on a sequence of near-X-Ramanujan graphs taken directly from the external O'Donnell-Wu construction. No equation or claim in the provided abstract or description reduces the rate bound Ω(ε^{2+o(1)}) to a parameter fitted inside the paper, a self-defined quantity, or a load-bearing self-citation chain. The central simplification (ordinary walks on distinct graphs) is presented as a new technique whose analysis composes with the cited external spectral properties; this is a standard non-circular use of prior results and qualifies as self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no explicit free parameters, axioms, or invented entities; the construction rests on the existence and properties of near-X-Ramanujan graphs from prior literature.

pith-pipeline@v0.9.0 · 5504 in / 1097 out tokens · 41112 ms · 2026-05-16T13:26:07.710094+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

free expander walks: ordinary expander walks where each step is taken on a distinct expander from a carefully chosen sequence derived from near-X-Ramanujan graphs
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

all-signings near-Ramanujan property and operator-norm bounds on Mw

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.