Bounds and Limitations on Codes Achieving List Recovery Capacity
Abstract
In coding theory, list recoverability is a fundamental concept which robustly captures how ``spread-out'' codewords are in a code. More formally, given a code C ⊆ Σn and input lists S1, …, Sn ⊆ Σ of size at most ℓ, list recoverability requires that there are at most L codewords c ∈ C such that ci ∈ Si for at least (1−ρ)n choices of i ∈ [n]. List recovery is an important question which has found applications in many areas, including complexity theory, property testing, compressed sensing, streaming algorithms, and cryptography. As our first main result, we establish a tight ``generalized singleton bound''. Formally, we show that for constant ℓ, L,ρ and sufficiently large alphabets Σ, if we define R*=(L+1−ℓ)/L−(L+1)/Lρ, it is possible for a (ρ,ℓ,L) list-recoverable code to have rate R*−ε but impossible to have rate R*+ε. One direction of our result already directly generalizes and improves a weaker impossibility result due to Goldberg, Shangguan, and Tamo. For our second main result, we prove that there is a fundamental shortcoming in existing methods that aim to construct explicit, optimal list-recoverable codes. Indeed, recent work has constructed explicit codes achieving list-decoding capacity (along with other related properties) using a framework introduced in the work of Alon--Edmonds--Luby (AEL). We give a meta-analysis of such constructions by presenting an ``AEL framework'' which captures all such recent constructions in the literature. Within this framework, we show that no AEL-based code can break a recently-identified list-recovery barrier for additive and linear codes.
Related
- Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time
- Capacity Achieving Torn Paper Codes
- Linear Programming Bounds for Locally Recovery Codes II
- Efficient capacity-achieving entanglement generation with application to pure-loss Bosonic channels
- On the Evolution of the Capacity-Achieving Input Support for the Amplitude-Constrained AWGN Channel
BibTeX
@misc{brakensiek2026bounds,
title = {{Bounds and Limitations on Codes Achieving List Recovery Capacity}},
author = {Joshua Brakensiek and Yeyuan Chen and Aaron Putterman and Zihan Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.19576},
eprint = {2607.19576},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.19576},
}
RIS
TY - UNPB
TI - Bounds and Limitations on Codes Achieving List Recovery Capacity
AU - Joshua Brakensiek
AU - Yeyuan Chen
AU - Aaron Putterman
AU - Zihan Zhang
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2607.19576
UR - https://arxiv.org/abs/2607.19576
AB - In coding theory, list recoverability is a fundamental concept which robustly captures how ``spread-out'' codewords are in a code. More formally, given a code C ⊆ Σ^n and input lists S_1, …, S_n ⊆ Σ of size at most ℓ, list recoverability requires that there are at most L codewords c ∈ C such that c_i ∈ S_i for at least (1−ρ)n choices of i ∈ [n]. List recovery is an important question which has found applications in many areas, including complexity theory, property testing, compressed sensing, streaming algorithms, and cryptography. As our first main result, we establish a tight ``generalized singleton bound''. Formally, we show that for constant ℓ, L,ρ and sufficiently large alphabets Σ, if we define R^*=(L+1−ℓ)/L−(L+1)/Lρ, it is possible for a (ρ,ℓ,L) list-recoverable code to have rate R^*−ε but impossible to have rate R^*+ε. One direction of our result already directly generalizes and improves a weaker impossibility result due to Goldberg, Shangguan, and Tamo. For our second main result, we prove that there is a fundamental shortcoming in existing methods that aim to construct explicit, optimal list-recoverable codes. Indeed, recent work has constructed explicit codes achieving list-decoding capacity (along with other related properties) using a framework introduced in the work of Alon--Edmonds--Luby (AEL). We give a meta-analysis of such constructions by presenting an ``AEL framework'' which captures all such recent constructions in the literature. Within this framework, we show that no AEL-based code can break a recently-identified list-recovery barrier for additive and linear codes.
ER -