The List Decoding Radius of Reed-Muller Codes over Small Fields

DOI10.1145/2746539.2746543MaRDI QIDQ2941515zbMATH OpenOpenAlexFDO

Authors Abhishek Bhowmick, Shachar Lovett

Publication date 21 August 2015

Published in Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.3433

zbMATH Keywords

weight distributioncoding theoryweak regularitylow-degree polynomialshigher-order Fourier analysislist-decoding algorithmSchwartz-Zippel extensions

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Decoding (94B35)

Abstract: The list decoding problem for a code asks for the maximal radius up to which any ball of that radius contains only a constant number of codewords. The list decoding radius is not well understood even for well studied codes, like Reed-Solomon or Reed-Muller codes. Fix a finite field $mathbbF$. The Reed-Muller code $mathrm{RM}_{mathbbF}(n,d)$ is defined by $n$-variate degree-$d$ polynomials over $mathbbF$. In this work, we study the list decoding radius of Reed-Muller codes over a constant prime field $mathbbF=mathbb{F}_p$, constant degree $d$ and large $n$. We show that the list decoding radius is equal to the minimal distance of the code. That is, if we denote by $delta(d)$ the normalized minimal distance of $mathrm{RM}_{mathbbF}(n,d)$, then the number of codewords in any ball of radius $delta(d)-varepsilon$ is bounded by $c=c(p,d,varepsilon)$ independent of $n$. This resolves a conjecture of Gopalan-Klivans-Zuckerman [STOC 2008], who among other results proved it in the special case of $mathbbF=mathbb{F}_2$; and extends the work of Gopalan [FOCS 2010] who proved the conjecture in the case of $d=2$. We also analyse the number of codewords in balls of radius exceeding the minimal distance of the code. For $eleqd$, we show that the number of codewords of $mathrm{RM}_{mathbbF}(n,d)$ in a ball of radius $delta(e)-varepsilon$ is bounded by $exp(ccdot{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] who proved similar bounds over $mathbb{F}_2$. The proof relies on several new ingredients: an extension of the Frieze-Kannan weak regularity to general function spaces, higher-order Fourier analysis, and an extension of the Schwartz-Zippel lemma to compositions of polynomials.

Recommendations

• The List Decoding Radius for Reed–Muller Codes Over Small Fields
• Bounds on the List-Decoding Radius of Reed--Solomon Codes
• List-Decodability With Large Radius for Reed-Solomon Codes
• List decodability at small radii
• On the List and Bounded Distance Decodability of Reed–Solomon Codes
• List Decoding of<tex>$q$</tex>-ary Reed–Muller Codes
• Upper Bound on List-Decoding Radius of Binary Codes
• Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius
• scientific article; zbMATH DE number 6850352
• scientific article; zbMATH DE number 2154515

Cites work

• Approximate distance oracles
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast C-K-R partitions of sparse graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On approximate distance labels and routing schemes with affine stretch
• On sparse spanners of weighted graphs
• Ramsey partitions and proximity data structures
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Shortest-path queries in static networks

Cited in

(5)

• On higher-order Fourier analysis over non-prime fields
• On the bias of Reed-Muller codes over odd prime fields
• scientific article; zbMATH DE number 7561763 (Why is no real title available?)
• The analytic rank of tensors and its applications
• scientific article; zbMATH DE number 6850352 (Why is no real title available?)

Describes a project that uses

Uses Software

• Graphs

This page was built for publication: The List Decoding Radius of Reed-Muller Codes over Small Fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941515)