TY - GEN
T1 - Better binary list-decodable codes via multilevel concatenation
AU - Guruswami, Venkatesan
AU - Rudra, Atri
PY - 2007
Y1 - 2007
N2 - We give a polynomial time construction of binary codes with the best currently known trade-off between rate and error-correction radius. Specifically, we obtain linear codes over fixed alphabets that can be list decoded in polynomial time up to the so called Blokh-Zyablov bound. Our work builds upon [7] where codes list decodable up to the Zyablov bound (the standard product bound on distance of concatenated codes) were constructed. Our codes are constructed via a (known) generalization of code concatenation called multilevel code concatenation. A probabilistic argument, which is also derandomized via conditional expectations, is used to show the existence of inner codes with a certain nested list decodability property that is appropriate for use in multilevel concatenated codes. A "level-by-level" decoding algorithm, which crucially uses the list recovery algorithm for folded Reed-Solomon codes from [7], enables list decoding up to the designed distance bound, aka the Blokh-Zyablov bound, for multilevel concatenated codes.
AB - We give a polynomial time construction of binary codes with the best currently known trade-off between rate and error-correction radius. Specifically, we obtain linear codes over fixed alphabets that can be list decoded in polynomial time up to the so called Blokh-Zyablov bound. Our work builds upon [7] where codes list decodable up to the Zyablov bound (the standard product bound on distance of concatenated codes) were constructed. Our codes are constructed via a (known) generalization of code concatenation called multilevel code concatenation. A probabilistic argument, which is also derandomized via conditional expectations, is used to show the existence of inner codes with a certain nested list decodability property that is appropriate for use in multilevel concatenated codes. A "level-by-level" decoding algorithm, which crucially uses the list recovery algorithm for folded Reed-Solomon codes from [7], enables list decoding up to the designed distance bound, aka the Blokh-Zyablov bound, for multilevel concatenated codes.
UR - https://www.scopus.com/pages/publications/38049077026
U2 - 10.1007/978-3-540-74208-1_40
DO - 10.1007/978-3-540-74208-1_40
M3 - Conference contribution
AN - SCOPUS:38049077026
SN - 9783540742074
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 554
EP - 568
BT - Approximation, Randomization, and Combinatorial Optimization
PB - Springer Verlag
T2 - 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007 and 11th International Workshop on Randomization and Computation, RANDOM 2007
Y2 - 20 August 2007 through 22 August 2007
ER -