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.
Versions