Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR02-024 | 24th April 2002 00:00

List-decoding in Linear Time

RSS-Feed




TR02-024
Authors: Piotr Indyk
Publication: 25th April 2002 01:41
Downloads: 1289
Keywords: 


Abstract:

Spielman showed that one can construct error-correcting codes capable
of correcting a constant fraction $\delta << 1/2$ of errors,
and that are encodable/decodable in linear time.
Guruswami and Sudan showed that it is possible to correct
more than $50\%$ of errors (and thus exceed the ``half of the minimum
distance barrier''), with polynomial-time encoding and decoding.
In this paper we show that it is possible to achieve these two properties
*simultanously*. Specifically, we give a construction of constant rate,
linear-time encodable codes that are capable of correcting any $\delta<2/3$
fraction of errors in linear time.
Our codes are constructed using high-quality expander graphs.



ISSN 1433-8092 | Imprint