Optimal rate list decoding over bounded alphabets using algebraic-geometric codes

DOI10.1145/3506668arXiv1708.01070MaRDI QIDQ6289740FDOQ6289740

Chaoping Xing, Venkatesan Guruswami

Publication date: 3 August 2017

Abstract: We give new constructions of two classes of algebraic code families which are efficiently list decodable with small output list size from a fraction $1-R-epsilon$ of adversarial errors where $R$ is the rate of the code, for any desired positive constant $epsilon$. The alphabet size depends only $epsilon$ and is nearly-optimal. The first class of codes are obtained by folding algebraic-geometric codes using automorphisms of the underlying function field. The list decoding algorithm is based on a linear-algebraic approach, which pins down the candidate messages to a subspace with a nice "periodic" structure. The list is pruned by precoding into a special form of "subspace-evasive" sets, which are constructed pseudorandomly. Instantiating this construction with the Garcia-Stichtenoth function field tower yields codes list-decodable up to a $1-R-epsilon$ error fraction with list size bounded by $O(1/epsilon)$, matching the existential bound up to constant factors. The parameters we achieve are thus quite close to the existential bounds in all three aspects: error-correction radius, alphabet size, and list-size. The second class of codes are obtained by restricting evaluation points of an algebraic-geometric code to rational points from a subfield. Once again, the linear-algebraic approach to list decoding to pin down candidate messages to a periodic subspace. We develop an alternate approach based on "subspace designs" to precode messages. Together with the subsequent explicit constructions of subspace designs, this yields a deterministic construction of an algebraic code family of rate $R$ with efficient list decoding from $1-R-epsilon$ fraction of errors over a constant-sized alphabet. The list size is bounded by a very slowly growing function of the block length $N$; in particular, it is at most $O(lo{g}^{(r)}N)$ (the $r$'th iterated logarithm) for any fixed integer $r$.

Mathematics Subject Classification ID

Computer science (68-XX)

This page was built for publication: Optimal rate list decoding over bounded alphabets using algebraic-geometric codes

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