期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：and Spielman (IEEE IT, 1996) showed that any (cd) -regular expander code with expansion parameter 43 is decodable in \emph{linear time} from a constant fraction of errors. Feldman et al. (IEEE IT, 2007)
proved that expansion parameter 32+13c is sufficient to correct a constant fraction of errors in \emph{polynomial time} using LP decoding.
In this work we give a simple combinatorial algorithm that achieves even better parameters. In particular, our algorithm runs in \emph{linear time} and works for any expansion parameter 32−16c.
