MathDB

Gopalan–Klivans–Zuckerman list-decoding radius conjecture for Reed–Muller codes

Let Pd(Fn)\mathcal{P}_{d}({\mathbb{F}}^n) be the class of polynomials of degree at most dd from Fn{\mathbb{F}}^n to F{\mathbb{F}}. For a function g:Fn→Fg:{\mathbb{F}}^n\to{\mathbb{F}}, let dist⁡\operatorname{dist} denote normalized Hamming distance, and define

ℓF(n,d,η):=max⁡g:Fn→F∣{f∈Pd(Fn):dist⁡(f,g)≤η}∣.\ell_{\mathbb{F}}(n,d,\eta):=\max_{g:{\mathbb{F}}^n\to{\mathbb{F}}}\left|\{f\in\mathcal{P}_d({\mathbb{F}}^n):\operatorname{dist}(f,g)\leq\eta\}\right|.

The list decoding radius LDR⁡F(n,d)\operatorname{LDR}_{\mathbb{F}}(n,d) is the maximum η\eta such that, for every ε>0\varepsilon>0, ℓF(n,d,η−ε)\ell_{\mathbb{F}}(n,d,\eta-\varepsilon) is bounded by a constant depending only on ε\varepsilon, ∣F∣|\mathbb{F}|, and dd. Let δF(d)\delta_{\mathbb{F}}(d) denote the relative minimum distance of the Reed–Muller code RM⁡F(n,d)\operatorname{RM}_{\mathbb{F}}(n,d). Gopalan–Klivans–Zuckerman's conjecture. For all constants dd and all fields F{\mathbb{F}},

LDR⁡F(n,d)=δF(d).\operatorname{LDR}_{\mathbb{F}}(n,d)=\delta_{\mathbb{F}}(d).

The conjecture asserts that Reed–Muller codes achieve list-decoding up to their minimum-distance bound over every finite field, extending the known binary result of Gopalan, Klivans, and Zuckerman. The source provides no resolution of the conjecture in the stated generality.

Sources & referencesView supporting material

Primary source

Abhishek Bhowmick and Shachar Lovett, “List decoding Reed-Muller codes over small fields”, arXiv:1407.3433 (2014).

coding-theorylist-decodingreed-muller-codes

Progress summary

Refreshed
Solved

A 2015 paper proved the conjecture for every fixed finite field, resolving it in its stated fixed-parameter setting.

Gopalan, Klivans, and Zuckerman posed the conjecture in 2008, asserting that Reed–Muller codes reach their minimum-distance limit for list decoding. They proved the binary case, while the general finite-field case remained open.

Known results

  • Binary fields, all fixed degrees (Gopalan, Klivans, and Zuckerman, 2008).
  • Degree d=2d=2, arbitrary finite fields (Gopalan, 2010).
  • Additional prime-field cases, including (p−1)∣d(p-1)\mid d, were known before the full prime-field result.

2015 general-field resolution

Bhowmick and Lovett stated and proved that for every fixed finite field K\mathbb{K} and fixed degree dd, LDR⁡K(n,d)=δK(d)\operatorname{LDR}_{\mathbb{K}}(n,d)=\delta_{\mathbb{K}}(d). Their paper explicitly describes this as resolving the Gopalan–Klivans–Zuckerman conjecture; no later objection, withdrawal, or retraction was found. A related work also treats growing field sizes.

Current status (as of August 2026): The equality LDR⁡F(n,d)=δF(d)\operatorname{LDR}_{\mathbb{F}}(n,d)=\delta_{\mathbb{F}}(d) is settled for every fixed finite field F\mathbb{F} and fixed degree dd, with no unresolved part of the stated conjecture recorded.

Sources

Solutions 0

No solutions have been posted yet.