Combinatorial Limitations of Average-Radius List Decoding

DOI10.1007/978-3-642-40328-6_41MaRDI QIDQ2851888zbMATH OpenOpenAlexFDO

Authors Srivatsan Narayanan, Venkatesan Guruswami

Publication date 4 October 2013

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Decoding (94B35)

Abstract: We study certain combinatorial aspects of list-decoding, motivated by the exponential gap between the known upper bound (of $O(1/gamma)$) and lower bound (of $Omeg{a}_p(log(1/gamma))$) for the list-size needed to decode up to radius $p$ with rate $gamma$ away from capacity, i.e., $1-h(p)-gamma$ (here $pin(0,1/2)$ and $gamma>0$). Our main result is the following: We prove that in any binary code $Csubseteq{0,1}^n$ of rate $1-h(p)-gamma$, there must exist a set $mathcalLsubsetC$ of $Omeg{a}_p(1/sqrtgamma)$ codewords such that the average distance of the points in $mathcalL$ from their centroid is at most $pn$. In other words, there must exist $Omeg{a}_p(1/sqrtgamma)$ codewords with low "average radius." The standard notion of list-decoding corresponds to working with the maximum distance of a collection of codewords from a center instead of average distance. The average-radius form is in itself quite natural and is implied by the classical Johnson bound. The remaining results concern the standard notion of list-decoding, and help clarify the combinatorial landscape of list-decoding: 1. We give a short simple proof, over all fixed alphabets, of the above-mentioned $Omeg{a}_p(log(gamma))$ lower bound. Earlier, this bound followed from a complicated, more general result of Blinovsky. 2. We show that one {em cannot} improve the $Omeg{a}_p(log(1/gamma))$ lower bound via techniques based on identifying the zero-rate regime for list decoding of constant-weight codes. 3. We show a "reverse connection" showing that constant-weight codes for list decoding imply general codes for list decoding with higher rate. 4. We give simple second moment based proofs of tight (up to constant factors) lower bounds on the list-size needed for list decoding random codes and random linear codes from errors as well as erasures.

Recommendations

• Combinatorial Limitations of Average-Radius List-Decoding
• Combinatorial bounds for list decoding
• On the Average Complexity of Reed–Solomon List Decoders
• Limits to List Decoding of Random Codes
• Average-radius list-recoverability of random linear codes
• Limits to List Decoding Reed–Solomon Codes
• Upper Bound on List-Decoding Radius of Binary Codes
• Bounds on the List-Decoding Radius of Reed--Solomon Codes
• Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius
• Limits to List Decoding Random Codes

Cited in

(5)

• List decodability at small radii
• Singleton-type bounds for list-decoding and list-recovery, and related results
• Average-radius list-recoverability of random linear codes
• Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

This page was built for publication: Combinatorial Limitations of Average-Radius List Decoding

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