Source-linked AI summary
List Decoding Expander-Based Codes via Fast Approximation of Expanding CSPs: I
Fernando Granha Jeronimo, Aman Singh
TL;DR
List decoding expander-based codes requires reconciling local candidate codewords, while naive enumeration considers ℓ^Θ(n) combinations. The paper applies weak regularity-based CSP approximation and shows that assignments constant on each decomposition part suffice, yielding a constant list-size bound beyond the trivial Johnson bound.
Problem
List decoding expander-based codes requires combining per-vertex candidate local codewords, while naive enumeration considers ℓ^Θ(n) combinations.
Source: §3 · p. 9Method
The paper models decoding through agreement CSPs on expander graphs and uses near-linear-time weak regularity approximation, enumerating assignments constant on each decomposition part.
Source: §1 · pp. 3–4Results
The paper establishes a constant bound on list size for the studied expander-based code constructions, beyond the trivial Johnson bound.
Source: §1 · p. 4Takeaways & Limitations
Assignments constant on each of the constantly many decomposition parts suffice to recover the list for the studied constructions.
Source: §1 · p. 4Decoding tasks for other code families are left to future work.
Source: §1 · p. 5
Abstract
from arXiv · showhide
We present near-linear time list decoding algorithms (in the block-length $n$) for expander-based code constructions. More precisely, we show that (i) For every $\delta \in (0,1)$ and $\epsilon > 0$, there is an explicit family of good Tanner LDPC codes of (design) distance $\delta$ that is $(\delta - \epsilon, O_\varepsilon(1))$ list decodable in time $\widetilde{\mathcal{O}}_{\varepsilon}(n)$ with alphabet size $O_\delta(1)$, (ii) For every $R \in (0,1)$ and $\epsilon > 0$, there is an explicit family of AEL codes of rate $R$, distance $1-R -\varepsilon$ that is $(1-R-\epsilon, O_\varepsilon(1))$ list decodable in time $\widetilde{\mathcal{O}}_{\varepsilon}(n)$ with alphabet size $\text{exp}(\text{poly}(1/\epsilon))$, and (iii) For every $R \in (0,1)$ and $\epsilon > 0$, there is an explicit family of AEL codes of rate $R$, distance $1-R-\varepsilon$ that is $(1-R-\epsilon, O(1/\epsilon))$ list decodable in time $\widetilde{\mathcal{O}}_{\varepsilon}(n)$ with alphabet size $\text{exp}(\text{exp}(\text{poly}(1/\epsilon)))$ using recent near-optimal list size bounds from [JMST25]. Our results are obtained by phrasing the decoding task as an agreement CSP [RWZ20,DHKNT19] on expander graphs and using the fast approximation algorithm for $q$-ary expanding CSPs from [Jer23], which is based on weak regularity decomposition [JST21,FK96]. Similarly to list decoding $q$-ary Ta-Shma's codes in [Jer23], we show that it suffices to enumerate over assignments that are constant in each part (of the constantly many) of the decomposition in order to recover all codewords in the list.
1 Introduction
The paper studies list decoding for expander-based codes, where locally valid codeword views must be assembled into globally consistent codewords. It uses fast approximation of agreement CSPs to obtain near-linear-time decoding results for Tanner and AEL codes.
1 Introduction
- Approximating CSPs on sufficiently expanding graphs enables the paper's near-linear-time approach to agreement CSPs arising from list decoding.The approach uses the weak regularity framework for CSPs from, based on a graph-partition technique developed by Frieze and Kannan.Source: §1 · p. 3
- Keeping local-code list sizes independent of block length keeps the CSP alphabet constant while allowing stronger expander degree and expansion.The paper states that stronger expansion does not degrade the parameters of AEL and Tanner constructions.Source: §1 · p. 3
- Weak regularity partitions CSP variables into constantly many parts, and enumerating assignments constant on each part suffices to recover the list.The paper extends this behavior from Ta-Shma's codes to other expander-based constructions, with a constant list-size bound.Source: §1 · p. 4
- Near-linear-time list decoding is given for Tanner codes up to designed distance and for AEL codes up to capacity.The introduction identifies these as the paper's first and second main results.Source: §1 · p. 4
- AEL list size can be improved to near-optimal O(1/ε) by using alphabet size exp(exp(poly(1/ε))) and the bound from [JMST25].The introduction also says the authors leave further list-size improvements for future work.Source: §1 · p. 4
- The paper frames its expander-code approach as a return from SOS distance certificates to a CSP perspective.Earlier AEL decoding up to capacity used SOS proofs and had O(n poly(1/ε)) running time [JMST25].Source: §1 · p. 5
- Decoding code families beyond those studied is left to future work.The paper specifically identifies other code families as an open direction.Source: §1 · p. 5
2 Preliminaries
The preliminaries establish how expander graphs, local-code constructions, and CSPs are represented. They also introduce weak regularity as a way to approximate functions on expanders using a partition-based decomposition.
2.1 Expander Graphs
- An (n, d, λ)-expander has neighborhoods that behave approximately like random samples of the opposite vertex set.The text formalizes this neighborhood property for subsets of either side of the bipartite graph.Source: §2.1 · p. 6
2.2 Codes
- AEL and Tanner codes combine expander graphs with local codes; the section states their rate and distance bounds and defines list decoding by radius and list size.It also defines code rate and distance and describes the local view at a graph vertex.Source: §2.2 · p. 7
2.3 Constraint Satisfaction Problems
- A 2-CSP assigns domain values to variables and checks whether each variable-pair assignment belongs to that pair’s allowed set.Source: §2.3 · p. 7
2.4 Weak Regularity Decomposition
- Factors partition a domain into atoms, and weak regularity approximates functions supported on expander edges by sums of cut functions.The decomposition can be found by a randomized algorithm; its approximation and running-time guarantees depend on the stated parameters.Source: §2.4 · p. 8
3 Technical Overview
The decoding problem is to stitch locally plausible codeword views into globally consistent codewords without enumerating exponentially many combinations. The paper encodes consistency as an expanding CSP, approximates its value using weak regularity, and enumerates a constant number of concentrated assignments.
Efficiently enumerating stitched local views
- Assignments corresponding to nearby codewords satisfy many consistency checks, and the decoder represents these checks as an expanding CSP over candidate local codewords.The naive alternative enumerates ℓ^Θ(n) combinations of local lists.Source: §3 · pp. 9, 11
Efficient Weak Regularity Decompositions
- Weak regularity approximates the CSP with a simple proxy, so enumeration checks only a constant number of relevant combinations rather than exponentially many local-view choices.The proxy is a constant-size sum of test functions, and its factors induce a constant number of parts.Source: §3 · pp. 9–10
- The proxy value depends on assignment distributions within factor parts, and preserving those distributions while changing assignments can sharply reduce satisfied constraints.This forces good assignments toward distributions concentrated on one choice per part.Source: §3 · p. 11
Efficiently enumerating stitched local views
- Enumerating delta-like distributions across the constant number of parts yields candidates close enough for unique decoding to recover every codeword in the target list.The enumeration has a constant number of iterations, ℓ^{2^{O(ℓ²/γ²)}}.Source: §3 · pp. 9, 11
4 List Decoding AEL Codes
The AEL decoder turns local lists into an agreement CSP and uses weak regularity to expose a concentrated structure that can be enumerated efficiently. Under suitable expansion, this gives near-linear-time list decoding close to the code's design distance.
4 List Decoding AEL Codes
- AEL codes built from a (δ_in, ℓ) list-decodable inner code and a uniquely decodable outer code are (δ_in − ε, ℓ²O(ℓ⁶/ε²)) list decodable under the stated expansion condition.If outer unique decoding takes time t, decoding takes eO_{ε,ℓ}(n + t).Source: §4 · p. 12
4.1 Setting up the CSP
- The decoder makes each CSP variable select a candidate local codeword, with edge constraints checking agreement between that codeword and the received edge symbol.The CSP value depends only on the left-side variables.Source: §4.1 · pp. 12–13
4.2 Weak Regularity Decomposition
- Weak regularity approximates the constraint functions by sums of cut functions, making CSP values depend only on assignment distributions over the induced factors.The factors are determined by the cut functions in the approximations.Source: §4.2 · p. 14
4.3 Concentration over Factors
- Any codeword within the decoding radius induces an assignment concentrated on the factor over its relevant left-side vertices.The concentration parameter is η = (5ℓ²γ/ε) · n/|S_z|.Source: §4.3 · p. 15
4.4 Covering relevant codewords
- Concentrated assignments let the algorithm enumerate measurable approximations and use the outer unique decoder to recover every relevant codeword.The resulting list size is at most ℓ²O(ℓ⁶/ε²), with near-linear time for fixed ε and ℓ.Source: §4.4 · p. 16
5 List Decoding Tanner Codes
For Tanner codes, the decoder treats choices from local lists as variables in an agreement CSP on the expander. Weak regularity and concentration then support efficient enumeration, yielding near-linear-time list decoding at a radius close to the designed distance.
5.1 Setting up the CSP
- The decoder assigns each vertex a candidate local codeword, and edge constraints test whether the chosen codewords agree on their shared edge symbol.It constructs a 2-CSP with 2n variables and domain [ℓ].Source: §5.1 · p. 18
5.2 Weak Regularity Decomposition
- Weak regularity makes the number of satisfied constraints in any edge subportion depend only on assignment distributions over the corresponding factors.The factors are built from the cut functions in the approximations.Source: §5.2 · pp. 18–19
5.3 Concentration over Factors
- A codeword within the decoding radius induces an assignment concentrated on the factor over its relevant right-side vertices.The concentration parameter is η = (5ℓ²γ/ε) · n/|T_z|.Source: §5.3 · p. 20
5 List Decoding Tanner Codes
- If C_0 is (δ_0, ℓ) list decodable, the Tanner code is (δ_0(δ_0 − ε), ℓ²O(ℓ⁶/ε⁶)) list decodable under the stated expansion condition, in eO_{ε,ℓ}(n) time.The result applies for constant 0 < ε < δ_0.Source: §5 · p. 18, §5.4 · p. 20
5.4 Covering relevant codewords
- The algorithm enumerates measurable approximations to concentrated assignments and invokes unique decoding to cover all relevant codewords.Its runtime is eO_{ε,ℓ}(n), and the list size is at most ℓ²O(ℓ⁶/ε⁶).Source: §5.4 · pp. 20–22
5.5 Instantiating the Code
- The explicit Tanner-code family is (δ_0² − ε, 2^{2O(ε⁻¹³)}) list decodable, with a probabilistic decoding algorithm running in 2^{2O(ε⁻¹³)} · e^{O(n)} time.Source: §5.5 · p. 22