Expander-based constructions of efficiently decodable codes

We present several novel constructions of codes which share the common thread of using expander (or expander-like) graphs as a component. The expanders enable the design of efficient decoding algorithms that correct a large number of errors through various forms of "voting" procedures. We consider both the notions of unique and list decoding, and in all cases obtain asymptotically good codes which are decodable up to a "maximum" possible radius and either (a) achieve a similar rate as the previously best known codes but come with significantly faster algorithms, or (b) achieve a rate better than any prior construction with similar error-correction properties. Among our main results are: Codes of rate Omega(epsilon (2)) over constant-sized alphabet that can be list decoded in quadratic time from (1 - epsilon) errors. This matches the performance of the best algebraic-geometric (AG) codes, but with much faster encoding and decoding algorithms. Codes of rate Q(epsilon) over constant-sized alphabet that can be uniquely decoded from (1/2 - epsilon) errors in near-linear time (once again this matches AG-codes with much faster algorithms). This construction is similar to that of [1], and our decoding algorithm can be viewed as a positive resolution of their main open question. Linear-time encodable and decodable binary codes of positive rate(1) (in fact, rate Omega(epsilon (4))) that can correct up to (1/4 - epsilon) fraction errors. Note that this is the best error-correction one can hope for using unique decoding of binary codes. This significantly improves the fraction of errors corrected by the earlier linear-time codes of Spielman [19] and the linear-time decodable codes of [18, 22].