MathDB

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

About 12 years old · traced to

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.

References

Primary source

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

coding-theorylist-decodingreed-muller-codes
Posted

Progress summary

Refreshed
Claimed 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.