Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-109 | 7th October 2007 00:00

Better Binary List-Decodable Codes via Multilevel Concatenation



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 (Guruswami-Rudra STOC06) 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 (Guruswami-Rudra STOC06), enables list decoding up
to the designed distance bound, aka the Blokh-Zyablov bound, for
multilevel concatenated codes.

ISSN 1433-8092 | Imprint