Venkatesan Guruswami and Atri Rudra

Better Binary List-Decodable Codes via Multilevel Concatenation

Abstract : 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. This work builds upon our previous work 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, enables list decoding up to the designed distance bound, aka the Blokh-Zyablov bound, for multilevel concatenated codes.