Lune

SODA2024Top-tier venue

AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets

Omar Alrabiah, Venkatesan Guruswami, Ray Li

Abstract

A simple, recently observed generalization of the classical Singleton bound to list-decoding asserts that rate R codes are not list-decodable using list-size L beyond an error fraction L L+1 (1-R) (the Singleton bound being the case of L = 1, i.e., unique decoding). We prove that in order to approach this bound for any fixed L > 1, one needs exponential alphabets. Specifically, for every L > 1 and R ∈ (0, 1), if a rate R code can be list-of-L decoded up to error fraction L L+1 (1-R-ε), then its alphabet must have size at least exp(Ω L,R (1/ε)). This is in sharp contrast to the situation for unique decoding where certain families of rate R algebraic-geometry (AG) codes over an alphabet of size O(1/ε 2 ) are unique-decodable up to error fraction (1 -R -ε)/2. Our bounds hold even for subconstant ε ≥ 1/n, implying that any code exactly achieving the Lth generalized Singleton bound requires alphabet size 2 ΩL,R(n) . Previously this was only known only for L = 2 under the additional assumptions that the code is both linear and MDS.

Our lower bound is tight up to constant factors in the exponent-with high probability random codes (or, as shown recently, even random linear codes) over exp(O L (1/ε))-sized alphabets, can be list-of-L decoded up to error fraction L L+1 (1 -R -ε).

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

6 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Generic Reed-Solomon Codes Achieve List-Decoding Capacity cites Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius
  • Generic Reed-Solomon Codes Achieve List-Decoding Capacity cites Randomly Punctured Reed-Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields
  • Randomly Punctured Reed-Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields cites Generic Reed-Solomon Codes Achieve List-Decoding Capacity
  • Generic Reed-Solomon Codes Achieve List-Decoding Capacity cites Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric
  • Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric cites Generic Reed-Solomon Codes Achieve List-Decoding Capacity
  • Generic Reed-Solomon Codes Achieve List-Decoding Capacity cites Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets
  • Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets cites Generic Reed-Solomon Codes Achieve List-Decoding Capacity
  • Randomly Punctured Reed-Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields cites Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius
  • Randomly Punctured Reed-Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields cites Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets
  • Explicit Codes Approaching Generalized Singleton Bound using Expanders cites Generic Reed-Solomon Codes Achieve List-Decoding Capacity
  • Explicit Codes Approaching Generalized Singleton Bound using Expanders cites Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius
  • Explicit Codes Approaching Generalized Singleton Bound using Expanders cites Randomly Punctured Reed-Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields
  • Explicit Codes Approaching Generalized Singleton Bound using Expanders cites Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds
  • Explicit Codes Approaching Generalized Singleton Bound using Expanders cites Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets
  • Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds cites Generic Reed-Solomon Codes Achieve List-Decoding Capacity
  • Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds cites Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius
  • Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds cites Randomly Punctured Reed-Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields
  • Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds cites Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric
  • Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds cites AG Codes Achieve List Decoding Capacity over Constant-Sized Fields
  • Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds cites Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets
  • Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric cites Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius
  • Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric cites Randomly Punctured Reed-Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields
  • Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric cites AG Codes Achieve List Decoding Capacity over Constant-Sized Fields
  • Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric cites Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets
  • AG Codes Achieve List Decoding Capacity over Constant-Sized Fields cites Generic Reed-Solomon Codes Achieve List-Decoding Capacity
  • AG Codes Achieve List Decoding Capacity over Constant-Sized Fields cites Randomly Punctured Reed-Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields
  • AG Codes Achieve List Decoding Capacity over Constant-Sized Fields cites Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets
  • Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets cites Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers6

  1. Generic Reed-Solomon Codes Achieve List-Decoding CapacityJoshua Brakensiek, Sivakanth Gopi, Visu MakamSTOC 2023 · 22 citations
  2. Explicit Codes Approaching Generalized Singleton Bound using ExpandersFernando Granha Jeronimo, Tushant Mittal, Shashank Srivastava, Madhur TulsianiSTOC 2025 · 9 citations
  3. AG Codes Achieve List Decoding Capacity over Constant-Sized FieldsJoshua Brakensiek, Manik Dhar, Sivakanth Gopi, Zihan ZhangSTOC 2024 · 6 citations
  4. Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton BoundsYeyuan Chen, Zihan ZhangSTOC 2025 · 2 citations
  5. Random Gabidulin Codes Achieve List Decoding Capacity in the Rank MetricZeyu Guo, Chaoping Xing, Chen Yuan, Zihan ZhangFOCS 2024 · 2 citations

Builds on4

  1. Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radiusChong Shangguan, Itzhak TamoSTOC 2020 · 27 citations
  2. Generic Reed-Solomon Codes Achieve List-Decoding CapacityJoshua Brakensiek, Sivakanth Gopi, Visu MakamSTOC 2023 · 22 citations
  3. Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size AlphabetsZeyu Guo, Zihan ZhangFOCS 2023 · 20 citations
  4. Randomly Punctured Reed-Solomon Codes Achieve List-Decoding Capacity over Linear-Sized FieldsOmar Alrabiah, Venkatesan Guruswami, Ray LiSTOC 2024 · 17 citations

Related papers

  1. Efficient list-decoding with constant alphabet and list sizesZeyu Guo, Noga Ron-ZewiSTOC 2021 · 21 citations
  2. List-decodability with large radius for Reed-Solomon codesAsaf Ferber, Matthew Kwan, Lisa SauermannFOCS 2021 · 17 citations
  3. Improved List Size for Folded Reed-Solomon CodesShashank SrivastavaSODA 2025 · 4 citations
  4. Combinatorial Bounds for List Recovery via Discrete Brascamp-Lieb InequalitiesJoshua Brakensiek, Yeyuan Chen, Manik Dhar, Zihan ZhangSTOC 2026 · 12 citations
  5. Improved Explicit Near-Optimal Codes in the High-Noise RegimesXin Li, Songtao MaoSODA 2025 · 1 citation
Dusk over the sea between two cliffs drawn in fine vertical lines