Abstract
This paper is motivated by the program of constructing list-decodable codes with linear-time encoding and decoding algorithms with rate comparable to or even matching the rate achieved by the best constructions with polynomial encoding/decoding complexity. We achieve this for three basic settings of list decoding, and view these as the first promising steps in the above general program.
First is a setting, which we call “mixture recovering”, where for each position, the symbols of ℓ codewords are given in a scrambled order, and the goal is to recover each of the ℓ codewords. This was one of the first models studied by Ar et al in their influential paper [5] and they gave a polynomial time solution with rate 1/ℓ using Reed-Solomon codes. We propose an elegant expander-based construction with rate Ω(1/ℓ) with linear-time encoding/decoding complexity.
Second is the setting of “list-recovering” where the input is a set of ℓ possibilities for the value at each coordinate of the codeword and the goal is to find all the consistent codewords. We give an explicit linear-time encodable/decodable construction which achieves rate that is polynomial in 1/ℓ (the best rate known for polynomial decoding complexity is Ω(1/ℓ)).
Third is the setting of decoding from erasures where a certain fraction of the symbols are erased and the rest are received intact. Here, for every ε > 0, we present an explicit construction of binary codes of rate Ω(ε 2 log − − O(1)(1/ε)) which can be encoded and list decoded from a fraction (1–ε) of erasures in linear time. This comes very close to the best known rate of Ω(ε 2) for polynomial decoding complexity. For codes over larger alphabets, we can even approach the optimal rate of Ω(ε) with linear time algorithms — specifically, we give linear-time list decodable codes of rate \(\tilde{\Omega}(\varepsilon^{1+1/a})\) over alphabet size 2a to recover from a fraction (1–ε) of erasures.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Albanese, A., Blomer, J., Edmonds, J., Luby, M., Sudan, M.: Priority encoding transmission. IEEE Transactions on Information Theory 42(6), 1737–1744 (1996)
Alekhnovich, M.: Linear diophantine equations over polynomials and soft decoding of Reed-Solomon codes. In: Proceedings of the Symposium on Foundations of Computer Science, pp. 439–448 (2002)
Alon, N., Bruck, J., Naor, J., Naor, M., Roth, R.: Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Transactions on Information Theory 38, 509–516 (1992)
Alon, N., Edmonds, J., Luby, M.: Linear time erasure codes with nearly optimal recovery. In: Proceedings of the 36th IEEE Symposium on Foundations of Computer Science, pp. 512–519 (1995)
Sigal, A., Lipton, R.J., Rubinfeld, R., Sudan, M.: Reconstructing algebraic functions from mixed data. SIAM Journal on Computing 28(2), 487–510 (1999)
Elias, P.: Zero error capacity under list decoding. Quarterly Progress Report, Research Laboratory of Electronics 48, 88–90 (1958)
Feng, G.L.: Two fast algorithms in the Sudan decoding procedure. In: Proceedings of the 37th Annual Allerton Conference on Communication, Control and Computing, pp. 545–554 (1999)
Guruswami, V.: List decoding from erasures: Bounds and code constructions. IEEE Transactions on Information Theory 49(11), 2826–2833 (2003)
Guruswami, V., Indyk, P.: Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. In: Proceedings of the Symposium on Theory of Computing, pp. 812–821 (2002)
Guruswami, V., Indyk, P.: Linear-time encodable and list-decodable codes. In: Proceedings of the Symposium on Theory of Computing, pp. 126–135 (2003)
Guruswami, V., Sudan, M.: Improved decoding of Reed-Solomon and algebraic-geometric codes. IEEE Transactions on Information Theory 45, 1757–1767 (1999)
Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8(3), 261–277 (1988)
Spielman, D.: Linear-time encodable and decodable error-correcting codes. IEEE Transactions on Information Theory 42(6), 1723–1732 (1996)
Sudan, M.: Decoding of Reed-Solomon codes beyond the error-correction bound. Journal of Complexity 13(1), 180–193 (1997)
Zémor, G.: On expander codes. IEEE Transactions on Information Theory 47(2), 835–837 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Guruswami, V., Indyk, P. (2004). Linear-Time List Decoding in Error-Free Settings. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds) Automata, Languages and Programming. ICALP 2004. Lecture Notes in Computer Science, vol 3142. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27836-8_59
Download citation
DOI: https://doi.org/10.1007/978-3-540-27836-8_59
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22849-3
Online ISBN: 978-3-540-27836-8
eBook Packages: Springer Book Archive