English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The list decoding problem for a code asks for the maximal radius up to whichany ball of that radius contains only a constant number of codewords. The listdecoding radius is not well understood even for well studied codes, likeReed-Solomon or Reed-Muller codes.  Fix a finite field $\mathbb{F}$. The Reed-Muller code$\mathrm{RM}_{\mathbb{F}}(n,d)$ is defined by $n$-variate degree-$d$polynomials over $\mathbb{F}$. In this work, we study the list decoding radiusof Reed-Muller codes over a constant prime field $\mathbb{F}=\mathbb{F}_p$,constant degree $d$ and large $n$. We show that the list decoding radius isequal to the minimal distance of the code.  That is, if we denote by $\delta(d)$ the normalized minimal distance of$\mathrm{RM}_{\mathbb{F}}(n,d)$, then the number of codewords in any ball ofradius $\delta(d)-\varepsilon$ is bounded by $c=c(p,d,\varepsilon)$ independentof $n$. This resolves a conjecture of Gopalan-Klivans-Zuckerman [STOC 2008],who among other results proved it in the special case of$\mathbb{F}=\mathbb{F}_2$; and extends the work of Gopalan [FOCS 2010] whoproved the conjecture in the case of $d=2$.  We also analyse the number of codewords in balls of radius exceeding theminimal distance of the code. For $e \leq d$, we show that the number ofcodewords of $\mathrm{RM}_{\mathbb{F}}(n,d)$ in a ball of radius $\delta(e) -\varepsilon$ is bounded by $\exp(c \cdot n^{d-e})$, where$c=c(p,d,\varepsilon)$ is independent of $n$. The dependence on $n$ is tight.This extends the work of Kaufman-Lovett-Porat [IEEE Inf. Theory 2012] whoproved similar bounds over $\mathbb{F}_2$.  The proof relies on several new ingredients: an extension of theFrieze-Kannan weak regularity to general function spaces, higher-order Fourieranalysis, and an extension of the Schwartz-Zippel lemma to compositions ofpolynomials.

List decoding Reed-Muller codes over small fields