Gopalan–Klivans–Zuckerman conjecture on Reed–Muller list-decoding radius

Let dd be fixed and let K\mathbb{K} be a finite field. For K\mathbb{K}, let textnormalLDRK(n,d)textnormal{LDR}_{\mathbb{K}}(n,d) denote the list-decoding radius of the Reed–Muller code, and let δK(d)\delta_{\mathbb{K}}(d) denote its normalized minimum distance, defined by writing d=a(q1)+bd=a(q-1)+b with 0b<q10\leqslant b<q-1 and setting

δK(d)=1qa(1bq),\delta_{\mathbb{K}}(d)=\frac{1}{q^a}\left(1-\frac{b}{q}\right),

where q=Kq=|\mathbb{K}|.

Gopalan–Klivans–Zuckerman conjecture. For fixed dd and finite field K\mathbb{K},

LDRK(n,d)=δK(d).\textnormal{LDR}_{\mathbb{K}}(n,d)=\delta_{\mathbb{K}}(d).

The right-hand side is the natural upper bound coming from the normalized minimum distance of Reed–Muller codes. Gopalan, Klivans, and Zuckerman proved the equality over F2\mathbb{F}_2; the conjecture asserts that the matching lower bound holds over every finite field.

Sources & referencesView supporting material

Primary source

Arnab Bhattacharyya and Abhishek Bhowmick, “Using higher-order Fourier analysis over general fields”, arXiv:1505.00619 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.