PaperlayerView exact revision on arXiv

Source-linked AI summary

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time

Shashank Srivastava, Madhur Tulsiani

arXiv:2504.20333v2cs.DScs.CCcs.ITmath.IT

TL;DR

Expander-based codes have fast unique decoding, but list decoding lacks general techniques at optimal rate-distance tradeoffs, and polynomial list sizes beyond Johnson were unknown for Tanner codes. This paper uses graph regularity to obtain near-linear list-decoding algorithms and new combinatorial bounds for AEL and Tanner codes.

  • Problem

    Fast list decoding of expander-based codes at optimal rate-distance tradeoffs remains limited, and polynomial list sizes beyond Johnson were unknown for Tanner codes.

    Source: §1 · pp. 3–4

  • Method

    The paper uses graph regularity lemmas to obtain near-linear-time list-decoding algorithms for AEL and Tanner codes.

    Source: §1.1 · p. 4

  • Results

    The framework gives near-linear-time list-decoding algorithms for AEL and Tanner codes, with new combinatorial list-size bounds beyond Johnson.

    Source: §1.1 · p. 4

  • Takeaways & Limitations

    The results provide combinatorial as well as algorithmic bounds for codes not previously known to be list decodable beyond the Johnson bound.

    Source: §1.1 · p. 4

    The AEL list-recovery bounds lose an exponential factor because the chosen random-linear inner codes have exponential list-size bounds.

    Source: §4.2.3 · p. 34

Abstract

from arXiv · show

We give a new framework based on graph regularity lemmas, for list decoding and list recovery of codes based on spectral expanders. Using existing algorithms for computing regularity decompositions of sparse graphs in (randomized) near-linear time, and appropriate choices for the constant-sized inner/base codes, we prove the following: - Expander-based codes constructed using the distance amplification technique of Alon, Edmonds and Luby [FOCS 1995] with rate $\rho$, can be list decoded to a radius $1 - \rho - \epsilon$ in near-linear time. By known results, the output list has size $O(1/\epsilon)$. - The above codes of Alon, Edmonds and Luby, with rate $\rho$, can also be list recovered to radius $1 - \rho - \epsilon$ in near-linear time, with constant-sized output lists. - The Tanner code construction of Sipser and Spielman [IEEE Trans. Inf. Theory 1996] with distance $\delta$, can be list decoded to radius $\delta - \epsilon$ in near-linear time, with constant-sized output lists. Our results imply novel combinatorial as well as algorithmic bounds for each of the above explicit constructions. All of these bounds are obtained via combinatorial rigidity phenomena, proved using (weak) graph regularity. The regularity framework allows us to lift the list decoding and list recovery properties for the local base codes, to the global codes obtained via the above constructions.

1 Introduction

The section develops a graph-regularity framework for combinatorial rigidity and near-linear-time list decoding and list recovery of expander-based codes, applying it to AEL and Tanner codes. It explains how local decoding and recovery properties lift to global codes and outlines the framework’s relation to earlier approaches and the algorithmic steps governing runtime.

1 Introduction

  • Expander codes have efficient unique-decoding algorithms, but list decoding has lacked general techniques exploiting expansion and optimal parameter tradeoffs.Beyond the Johnson bound, algebraic structure has supplied list-size bounds, but may be unavailable for expander codes or incompatible with other desired properties.Source: §1 · pp. 3–4

1.1 Our results

  • Graph regularity yields combinatorial rigidity that supports near-linear-time list decoding for AEL and Tanner codes and new list-size bounds beyond the Johnson bound.The framework captures edge-counting arguments used in expander-code proofs and turns them into algorithmic analogues.Source: §1.1 · p. 4, §1.2 · p. 8

1.1.1 Alon-Edmonds-Luby (AEL) codes

  • AEL codes can be list decoded near the capacity radius 1 − ρ − ε in near-linear time, and list recovered to that radius under inner-code and outer-code conditions.The list-decoding guarantee uses an inner code with bounded list sizes and assumes near-linear-time unique decoding for the outer code; list recovery assumes outer-code unique decoding and inner-code list-recovery bounds.Source: §1.1.1 · pp. 5–6

1.1.2 Tanner codes

  • For Tanner codes based on [SS96], bounded base-code lists enable near-linear-time decoding beyond the Johnson bound, reaching radius δ² − 2ε when the base code decodes to at least δ − ε.The stated theorem gives radius δ · δdec − ε when the expander parameter satisfies λ ≤ c · ε^4/K^4, for a small constant c.Source: §1.1.2 · pp. 7–8

1.2 Technical overview

  • The technical approach adapts expander edge-counting proofs by using graph regularity lemmas to capture edge counts for subgraphs of expanding graphs.The motivation is that distance and other local-to-global proofs estimate edges between carefully chosen vertex subsets using the expander mixing lemma.Source: §1.2 · p. 8
  • Enumerating signatures of agreement-graph sets finds AEL list codewords and gives a combinatorial list-size bound of (1/η)^|F|.Signatures discretized at constant parameters form a net; nearby candidate sets can be corrected by unique decoding in the outer code.Source: §1.2 · pp. 9–10
  • For Tanner codes, two-sided local lists and agreement graphs yield rigid candidate sets, with uncovered locations treated as erasures for unique decoding.The argument also extends to asymmetric Tanner codes with different left and right base codes.Source: §1.2 · p. 10
  • AEL list recovery uses agreement graphs between inner-code lists and input right-vertex lists, then applies rigidity to recover globally consistent codewords.The authors suggest that two-sided list recovery for base codes may extend the approach to Tanner codes.Source: §1.2 · p. 11
  • Regularity decompositions stitch local lists into globally consistent codewords, lifting local list-size bounds both combinatorially and algorithmically.The framework strengthens edge-density conditions to matching densities across regularity partitions, which implies that the corresponding sets agree almost everywhere.Source: §1.2 · pp. 11–12
  • Regularity decomposition is the only component requiring near-linear rather than linear time; after local lists are computed, the algorithm is alphabet-size independent.The decomposition can also be computed deterministically in O(n^3.5) time; other algorithm components are deterministic and linear-time.Source: §1.2 · p. 11

1.3 Related work

  • Earlier expander decoding by Guruswami and Indyk used repetition inner codes, causing rate decay as exp(-exp(1/ε^3)).The paper describes its results as sparse analogues of tensor-code list decoding; unlike prior hypergraph-regularity applications, its focus is decoding from an optimal fraction of errors.Source: §1.3 · p. 12

2 Preliminaries

The preliminaries set up codes, distances, and expander graphs, then introduce factors and signature coverings used to organize later arguments.

2.1 Codes and distances

  • A code is described by its block length, distance, and rate, while L(g, β) denotes codewords within distance β of g.The section also defines left and right distances for edge-labelings of a bipartite graph.Source: §2.1 · p. 13

2.2 Expander graphs

  • An (n, d, λ)-expander is a d-regular bipartite graph whose spectral parameter is its biadjacency matrix’s second-largest singular value.The expander mixing lemma is stated as a property of these graphs.Source: §2.2 · p. 14

2.3 Factors, signatures, and enumeration

  • A factor is a partition of X, and a function measurable with respect to it is constant on each partition cell.Conditional averages over the cells produce factor-measurable functions.Source: §2.3 · p. 14
  • Function factors group points by Boolean-function values, while signature nets provide finite coverings of function correlations.The net size for K-tuples is at most (1/η + 1)^(K·|F|).Source: §2.3 · p. 15

3 Regularity Lemmas for Subgraphs of Expanders

The section develops regularity decompositions for subgraphs of expanders and turns them into efficiently constructible function families that support later algorithms.

3 Regularity Lemmas for Subgraphs of Expanders

  • For any bipartite graph G = (L, R, E), subgraph H, and γ > 0, the Existential Regularity Lemma guarantees p ≤ 1/γ^2 triples (c_i, S_i, T_i).Their real weights satisfy ∑_{i=1}^p |c_i| ≤ 1/γ.Source: §3 · p. 17

3.1 Efficient regularity lemma

  • For a subgraph of an expander, an efficient regularity decomposition is available under a spectral condition, with randomized near-linear or deterministic O(|E(G)|^3.5) runtime.The construction uses an approximation to the cut-norm problem, which is NP-hard to solve exactly in general.Source: §3.1 · pp. 18, 20

3.2 Function families given by regularity lemma

  • A function family is (η, γ)-regular when closeness in its function-family distance implies edge-count closeness for every right-side set.For subgraphs of expanders, such families are constructible in randomized near-linear or deterministic O(|E(G)|^3.5) time when γ is sufficiently large relative to λ.Source: §3.2 · pp. 20–21

4 Algorithms for AEL Codes

The AEL construction combines outer and inner codes through an expander graph. Its distance bound and parameter regime explain how it can retain the inner code’s distance while keeping rate close to the inner rate.

4 Algorithms for AEL Codes

  • AEL coding concatenates an outer code with an inner code, shuffles symbols along expander edges, then folds the symbols at right vertices into the final code.Each outer-code codeword gives a unique AEL codeword.Source: §4 · p. 22
  • With a high-rate outer code and sufficiently small λ, the AEL code’s rate is close to the inner-code rate and its distance can approach the inner-code distance.The text notes that this yields an infinite explicit family inheriting parameters from a small constant-sized code.Source: §4 · pp. 22–23
  • The AEL code has distance at least δ_in − λ/δ_out.The bound relates inner and outer code distances to the expander parameter.Source: §4 · p. 22

4.1 List decoding AEL codes up to capacity

This section presents list decoding for AEL codes, using graph regularity to turn local inner-code lists into consistent global codewords. It also specifies bounds on the code alphabet size and parity-check size.

4.1.1 Picking from local lists via regularity

  • If β ≤ δin − ε, λ ≤ γ, and disjoint sets Si are η-close to Ai on a simultaneously (η, γ)-regular family, then ∑i|Si \ Ai| ≤ (2Kγ/ε)·n.The sets Ai mark each local list's position for the true codeword; rigidity bounds the erroneous choices among candidate sets.Source: §4.1.1 · p. 24

4.1.2 The list decoding algorithm

  • For β ≤ δin − ε, constant inner-list bound K, and λ ≤ ε·δdec/(4K), the algorithm outputs all codewords within β in time O(n·Tlocal(β + ε) + K·Treg(γ)) + Tdec·(1/γ)^{O(K²/γ²)}, where γ = ε·δdec/(4K).Its output list is bounded by (1/γ)^{O(K²/γ²)}.Source: §4.1.2 · p. 25

4.1.3 Instantiating AEL codes for list decoding

  • For any g ∈ (Fd_q)^R, an algorithm outputs L(g, 1 − ρ − ε) in time eO_ε(n); this list has size at most exp(O(1/ε^17)).Source: §4.1.3 · p. 27
  • The AEL code alphabet size is 2^O(1/ε^22).The passage gives q_d = 2^O(1/ε^2)·O(1/ε^20) = 2^O(1/ε^22).Source: §4.1.3 · p. 28
  • The AEL code has parity checks of size at most O(1/ε^23).Choosing C_out as Tanner codes of rate 1 − ε/4 gives parity checks of size at most O(1/ε^3), yielding O(d·(1/ε^3)) = O(1/ε^23) for C_AEL.Source: §4.1.3 · p. 28

4.2 List recovering AEL codes up to capacity

This section develops regularity-based list recovery for explicit AEL codes, combining local lists with outer-code unique decoding to reach radius 1 − ρ − ε in near-linear time with constant-sized output lists. It also instantiates the construction with random linear inner codes, whose exponential list-size loss preserves linearity and enables list-recovery-capacity LDPC codes.

4.2.1 Picking from local lists via regularity

  • Expander mixing places each qualifying codeword in most local lists, while a rigidity lemma identifies the corresponding assignments when β ≤ δ_in − ε and λ ≤ γ.Claim 4.10 bounds the fraction of missing local lists by γ when λ ≤ γ·ε; Lemma 4.11 bounds extraneous assignments by (3kKγ/ε)·n.Source: §4.2.1 · pp. 29–30

4.2.2 The list recovery algorithm

  • The algorithm forms local lists, uses kK regularity computations to identify consistent assignments, and invokes the outer unique decoder to recover all qualifying codewords.Its assumptions include inner-code list recovery through β + ε with output size at most K, β ≤ δ_in − ε, and sufficiently small expander λ.Source: §4.2.2 · p. 31

4.2.3 Instantiating AEL codes for list recovery

  • If the inner code list recovers through radius δ_in − ε with bounded output size and the outer code is uniquely decodable, AEL list recovery reaches radius δ_in − 2ε.The theorem’s instantiation uses a sufficiently small expander parameter and yields a constant-sized output list.Source: §4.2.3 · pp. 32–33
  • Explicit AEL codes of rate ρ list recover from radius 1 − ρ − ε in time eO_{k,ε}(n), with constant-sized output lists.The result holds for input lists of size at most k.Source: §4.2.3 · p. 33
  • The inner code has list size at most K = (8k/ε)^(8k/ε), and the resulting AEL code has rate at least ρ.The rate bound follows from ρ(C_AEL) ≥ (1 − ε/4)(ρ + ε/4) ≥ ρ.Source: §4.2.3 · pp. 33–34
  • The AEL code can be list recovered up to radius 1 − ρ − ε in time Õ(nq^d + kKn).Here K is the inner-code list-size bound and q^d is the code alphabet size.Source: §4.2.3 · p. 34
  • The list-recovery bounds lose an exponential factor because the random linear inner codes have larger lists than optimal, while preserving linearity supports LDPC codes at list-recovery capacity.Random nonlinear inner codes achieve list size O(k/ε), whereas the random linear codes used here have list size (k/ε)^O(k/ε) [LS25].Source: §4.2.3 · p. 34

5 Algorithms for Tanner Codes

This section studies list decoding for Tanner codes by lifting local-code decoding through graph regularity. It gives a near-linear-time radius of δ·δdec−ε under a sufficiently small-expansion condition, and reaches δ² when the local code is decodable up to its distance δ.

5 Algorithms for Tanner Codes

  • Tanner-code distance is at least √(δLδR), approaching δLδR as λ shrinks; under the stated erasure condition, unique decoding runs in linear time when 2ΔL+s≤δR−4ε.For linear inner codes, the Tanner-code rate is at least ρL+ρR−1.Source: §5 · p. 34, A Errors-and-Erasures Decoding of… · p. 44
  • With identical inner codes of distance δ, decoding reaches δ·J(δ), beyond the Johnson bound; if the inner code decodes to δ, Tanner codes decode to their designed distance δ^2.J(δ) is the Johnson bound for distance δ, and λ must be sufficiently small.Source: §5 · p. 35

5.1 List decoding Tanner codes

  • Decoding each left and right neighborhood produces bounded-size local lists, and a sufficiently close Tanner-code word is absent from at most δR−ε left lists and δL right lists.The local decoders operate to radii δdec_L and δdec_R, respectively.Source: §5.1 · p. 35

5.1.1 Picking from local lists via regularity

  • Simultaneous regularity across compatibility subgraphs makes candidate disjoint vertex sets close to the true local-list position sets, enabling recovery with errors-and-erasures decoding.The compatibility subgraphs are formed from pairs of local-list entries that agree on their shared edges.Source: §5.1.1 · p. 36

5.1.2 The list decoding algorithm for Tanner codes

  • The algorithm enumerates regularity-derived candidate sets and applies the errors-and-erasures unique decoder to recover every codeword in the target list.Its enumeration uses K1K2 regularity computations and a constant number of unique-decoder calls, with the call count depending on ε, K1, and K2.Source: §5.1.2 · pp. 37, 39

5.2 Main result for Tanner codes

  • For one constant-alphabet code of distance at least δ and list size K independent of d, Tanner codes decode to radius δ·δdec−ε in eO(n) time with list size at most exp(O(K^9/ε^3)), when λ≤c·ε^4/K^4.The local code must be list decodable to radius δdec; c is a sufficiently small constant.Source: §5.2 · p. 39
  • If C0 is decodable up to its distance δ, then CTan is decodable up to δ^2.Source: §5.2 · p. 40

A Errors-and-Erasures Decoding of Tanner Codes

Tanner-code decoding alternates local corrections on the two sides of the expander, moving the candidate toward a nearby codeword. Under the stated distance condition, the codeword is unique and can be recovered in linear time.

A Errors-and-Erasures Decoding of Tanner Codes

  • If 2∆L(g, h) + s ≤ δR − 4ε, at most one Tanner codeword satisfies the condition, and the algorithm outputs it in linear time when one exists.The stated running time is O(n · |Σ|d).Source: A Errors-and-Erasures Decoding of… · p. 44
  • The algorithm alternates local decoding on right and left neighborhoods, forming a sequence of candidates intended to move closer to the target codeword.It first projects the received word onto local right-code neighborhoods; the initial correction handles errors and erasures, while later steps analyze errors.Source: A Errors-and-Erasures Decoding of… · p. 44
  • Expander-based correction makes the candidate distances decrease until an iterate converges to the target after Θ(log n) steps.The analysis bounds how many neighborhoods see too many disagreements, using expander mixing and alternating correction claims.Source: A Errors-and-Erasures Decoding of… · pp. 45–46
  • The iterative procedure runs in O(log n · |Σ| · n) time, while updating only changed neighborhoods yields a linear-time implementation.The per-iteration bound assumes worst-case local decoding cost |Σ|d; the text says this is constant for constant-sized Σ.Source: A Errors-and-Erasures Decoding of… · p. 46
Loading 2504.20333v2…