Probabilistic Guarantees to Explicit Constructions: Local Properties of Linear Codes

• Explicit constructions are sought after existential proofs establish desirable parameter trade-offs, especially because certifying minimum distance and decoding can be computationally hard.Source: §1 · p. 3
• The motivating question is whether existential results for codes can be converted into explicit constructions through a general procedure.Source: §1 · p. 3
• The existential-to-explicit gap has historically lasted decades, including between Shannon’s capacity result and polar codes [Ari09], and between the Gilbert–Varshamov bound and Ta-Shma’s construction.Source: §1 · p. 3
• The framework gives explicit constructions for local properties—including list decoding, list recovery, perfect hashing, and average pairwise distance—while preserving random-linear-code parameters at increased alphabet size.Source: §1 · p. 3
• The framework builds on the AEL construction, a local-to-global approach that combines a constant-sized object with a constructed family to transfer a desired property.Source: §1 · pp. 3–4

Alon-Edmonds-Luby (AEL) Construction.

• AEL concatenates an explicit outer code with a brute-force inner code, then permutes symbols according to an expander to lift the inner code’s distance to the final code.The AEL procedure uses a constant-sized inner code with strong parameters and an explicit outer code that may have weaker parameters.Source: Alon-Edmonds-Luby (AEL) Construction · p. 4

1.1 Our Results

• LCL properties provide a formulation for studying local properties of large-alphabet random linear codes, where the earlier formulation in [MRR+20] did not apply.The LCL framework also establishes threshold results and an equivalence between random Reed–Solomon and random linear codes for these properties.Source: §1.1 · p. 5
• For any LCL property, suitable inner and outer codes plus a bipartite expander yield an explicit code avoiding the property at a rate arbitrarily close to its threshold.The resulting constructions are LDPC codes and achieve parity with random linear codes on LCL parameters.Source: §1.1 · p. 5
• The construction enlarges alphabet size exponentially in q0^poly(L/ε), and the resulting codes are linear only over the inner code’s subfield.The paper says subfield-linearity does not pose difficulties for most applications.Source: §1.1 · p. 5
• For list-recovery at capacity, the construction has smaller output list sizes than with [Tam24] and, at the cost of a larger alphabet; versus, list-size bounds match while its alphabet remains constant rather than polynomial in block length.The paper also reports a modest alphabet-size improvement over [JMST25] for explicit list-decodable codes approaching the Generalized Singleton Bound.Source: §1.1 · pp. 7–8
• Explicit list-recoverable codes match the smallest output list sizes attained by random linear codes, at rate R−2ε and alphabet size at most exp((L/ε)^O(L)).The construction assumes an outer code with rate 1−ε and distance ε^3, rather than strong list-size guarantees.Source: §1.1 · p. 7
• The framework also gives explicit zero-error and erasure list-recoverable codes with rate R−2ε and output list sizes matching those of random linear codes.It also yields explicit linear perfect hash matrices with Q = exp(t^t) entries over F_Q.Source: §1.1 · p. 8
• The AEL-based constructions admit efficient list decoding using recently developed AEL decoders based on the Sum-of-Squares hierarchy and regularity lemmas.The stated decoding tractability follows from the expander graphs used in AEL.Source: §1.1 · pp. 8–9

2 Technical Overview

• AEL-based list-decoding analysis transfers agreement patterns through an expander, but projected codewords may not be pairwise distinct, so the inner code’s guarantee cannot be applied directly.The agreement hypergraph represents which codewords agree with the received word at each coordinate.Source: §2 · p. 10
• A weakly-partition-connected hypergraph lets the construction select a non-trivial subset of codewords whose constraints transfer to inner-code projections and contradict the inner code’s property.The projected constraints occur on more than (1 − δout)n left vertices, forcing at least one non-trivial set of inner codewords.Source: §2 · p. 10
• An LCL property is specified by local profiles of coordinate-wise linear constraints, and a code satisfies it when it contains a vector set represented by one such profile.The profile’s constraints apply to rows of an n × L matrix.Source: §2 · p. 10
• Figure 1 depicts constraint types by color and compares how often several inner-code copies witness the constraints with the vector set on the right.The caption says the proportions are roughly the same.Source: Figure 1 · p. 11
• Implied local profiles compress the vector sets associated with a local profile; linearity ensures a code containing the original set also contains one satisfying its implied profile.The AEL analysis uses expander sampling to transfer implied-profile constraints to inner-code projections.Source: §2 · p. 11

3 Preliminaries

• LDist(V) contains subspaces with, for every pair of distinct coordinates, a vector whose entries differ at those coordinates.The preliminaries also define kernels of linear maps and use 0 for the all-zero matrix.Source: §3 · p. 12

3.1 Error-Correcting Codes

• Concatenating Cout and Cin gives block length Nd, rate Rout · Rin, and distance δout · δin.The outer-code symbols are encoded individually using a bijection from Σout to Cin.Source: §3.1 · p. 13

3.2 Alon-Edmonds-Luby (AEL) Construction

• The AEL construction uses a polynomial-time-constructible bipartite expander whose sampler property transfers right-side densities to left-side neighborhoods.The construction is polynomial-time when its components are, and it is LDPC if Cout is LDPC.Source: §3.2 · pp. 13–14

4.1 Preliminaries

• A list-decoding configuration with average Hamming distance at most L/(L+1)(1−R)n yields a subset of at least two vectors whose agreement hypergraph is (R,n)-weakly-partition-connected.This connects a global decoding obstruction to the hypergraph condition used by the rank argument.Source: §4.1 · p. 14
• For each agreement hypergraph of size at most L+1 that is (R+ε/2,n)-weakly-partition-connected, an Fq-linear code exists whose only codewords satisfying every agreement are all equal.The random-matrix guarantee gives full column rank for the corresponding substituted reduced intersection matrices.Source: §4.1 · p. 16

4.2 Proof for List-Decoding

• If a global agreement hypergraph is (R+ε,N)-weakly-partition-connected, then more than (1−δout)N left vertices have local projections whose agreement hypergraphs are (R+ε/2,d)-weakly-partition-connected.The proof retains sufficiently frequent agreement types when transferring the structure to local projections.Source: §4.2 · pp. 17–18
• Under Rout=1−ε and δout≥ε^3, CAEL is an Fq-linear LDPC average-radius list-decodable code with rate R_AEL=R(1−ε)>R−ε.The construction uses Q=q^d.Source: §4.2 · pp. 17, 19

5 Constructions for Local Properties

• Local profiles use matrix constraints and frequency-based descriptions, allowing LCL properties to apply across different field sizes and to be described independently of block length.The matrix constraints act on vectors over an extension field, while each matrix’s fraction of coordinates is specified in the profile description.Source: §5 · p. 20

5.1 Preliminaries

• A random linear code contains a local profile with exponentially low probability below its threshold rate and with probability exponentially close to 1 above it.The stated behavior holds for rates a constant ε below or above the threshold, respectively.Source: §5.1 · p. 23
• Including all coordinate permutations of a local profile description preserves its threshold rate, though it increases the alphabet size by a constant amount.The threshold depends on matrix frequencies rather than their order.Source: §5.1 · p. 24

5.2 Implied Local Profile Descriptions

• Robust profiles permit up to a Δ fraction of constraints to be dropped; avoiding them ensures a code also avoids matrices satisfying only a (1 − Δ) fraction of V’s constraints.Any matrix satisfying V also satisfies every profile in RobΔ(V).Source: §5.2 · p. 25
• When the rate is ε below the threshold RV, the potential of robust counterparts of Vimp is bounded above by −ε, up to a small additive factor.Source: §5.2 · p. 25
• For R ≤ RP − ε, a prime power q depending only on ε, L, q0, and P yields a code for every n ≥ 4L^2/ε that avoids nonzero robust implied-profile matrices and does not satisfy P.The code can be found in time qpoly(n,L).Source: §5.2 · p. 28

5.3 Main Result

• The AEL code CAEL(Cin,Cout,G) is Fq-linear and does not satisfy P when Cin is the code guaranteed by Fact 5.30.The theorem considers CAEL as a code over FQ, where Q = q^d.Source: §5.2 · p. 28, §5.3 · p. 29
• For each index in L*, Claim 5.33 supplies a witness Vimp whose robust local profile follows from the approximate proportions of rows lying in ker Mt.The proof relates incoming-edge proportions for each St to row proportions in the corresponding kernels, then accounts for deviations with a robust local profile.Source: §5.3 · pp. 30–31
• A nonzero projected-code column and an index in S ∩ L* yield a contradiction to the guarantee from Fact 5.30.The proof notes that projected columns are codewords and uses Claim 5.33 to find an index in the intersection.Source: §5.3 · p. 30
• More than (1 − δout)N indices have incoming-neighbor coverage at least (ft − η)d for every t ∈ Tβ.This is the bound stated in Eq. (16).Source: §5.3 · p. 31

6 Consequences

• For an L-LCL property P, the AEL construction gives an explicit Fq-linear LDPC code avoiding P with rate greater than RP − 2ε.The construction takes polynomial time in N.Source: §6 · pp. 32–33
• Taking the union of local profile descriptions lets one construction avoid satisfying any of several L-LCL properties simultaneously.The properties must use constraints over the same field Fq0.Source: §6 · p. 33

6.1 List Recovery

• Because failure of average-radius list recovery with erasures is an (L + 1)-LCL property, Corollary 6.1 yields explicit codes that are average-radius list-recoverable with erasures.Corollary 6.10 gives rate greater than RP − 2ε and polynomial-time construction.Source: §6.1 · pp. 34, 36
• The construction also gives explicit codes for list recovery at capacity, zero-error list recovery, and list recovery from erasures, with rates tied to the corresponding RP bounds.Each stated rate exceeds its corresponding RP value by less than 2ε.Source: §6.1 · p. 36
• Using the construction for P(0, 0, t − 1, t − 1) yields perfect hash matrices with alphabet size at most exp((t/ε)O(t)).The codewords arranged as columns form the perfect hash matrix.Source: §6.1 · p. 36

6.2 Efficient Decoding Algorithms

• AEL decoding relies on a sufficiently expanding graph; weak-regularity-based decoders run in near-linear time, while Sum-of-Squares-based decoders have larger polynomial running time.The stated requirement is a sufficiently small second-largest singular value of the graph's (bi)adjacency matrix.Source: §6.2 · p. 37
• The AEL codes admit efficient list decoding with near-linear time under the stated construction, and can also satisfy complements of additional LCL properties.The list-decoding result uses an inner code avoiding the property at the ε-relaxed Generalized Singleton Bound and an outer code with linear-time decoders.Source: §6.2 · p. 37
• AEL list-recovery decoding runs in e Oε,ℓ,Lin(n + T) time when the outer code decodes in time T.The resulting codes can achieve near-linear-time list recovery up to the optimal bound.Source: §6.2 · p. 37