Abstract
We prove the following results concerning the list decoding of error-correcting codes:
-
1
We show that for any code with a relative distance of δ (over a large enough alphabet), the following result holds for random errors: With high probability, for a ρ ≤ δ − ε fraction of random errors (for any ε> 0), the received word will have only the transmitted codeword in a Hamming ball of radius ρ around it. Thus, for random errors, one can correct twice the number of errors uniquely correctable from worst-case errors for any code. A variant of our result also gives a simple algorithm to decode Reed-Solomon codes from random errors that, to the best of our knowledge, runs faster than known algorithms for certain ranges of parameters.
-
1
We show that concatenated codes can achieve the list decoding capacity for erasures. A similar result for worst-case errors was proven by Guruswami and Rudra (SODA 08), although their result does not directly imply our result. Our results show that a subset of the random ensemble of codes considered by Guruswami and Rudra also achieve the list decoding capacity for erasures. We also show that the exponential list size bound in our result with outer random linear codes cannot be improved using the recent techniques of Guruswami, Håstad and Kopparty that achieved similar improvements for errors.
Our proofs employ simple counting and probabilistic arguments.
Research supported by NSF CAREER Award CCF-0844796.
This is a preview of subscription content, log in via an institution to check access.
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
Dumer, I., Micciancio, D., Sudan, M.: Hardness of approximating the minimum distance of a linear code. IEEE Transactions on Information Theory 49(1), 22–37 (2003)
Gál, A., Halevi, S., Lipton, R.J., Petrank, E.: Computing from partial solutions. In: Proceedings of the 14th Annual IEEE Conference on Computation Complexity, pp. 34–45 (1999)
Guruswami, V., Rudra, A.: Explicit codes achieving list decoding capacity: Error-correction up to the Singleton bound. IEEE Transactions on Information Theory 54(1), 135–150 (2008)
Guruswami, V., Sudan, M.: List decoding algorithms for certain concatenated codes. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), pp. 181–190 (2000)
Guruswami, V.: List decoding from erasures: bounds and code constructions. IEEE Transactions on Information Theory 49(11), 2826–2833 (2003)
Guruswami, V. (ed.): List Decoding of Error-Correcting Codes. LNCS, vol. 3282. Springer, Heidelberg (2004)
Guruswami, V., Håstad, J., Kopparty, S.: On the list-decodability of random linear codes. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC (to appear, 2010)
Guruswami, V., Rudra, A.: Concatenated codes can achieve list-decoding capacity. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 258–267 (2008)
Guruswami, V., Rudra, A.: Better binary list decodable codes via multilevel concatenation. IEEE Transactions on Information Theory 55(1), 19–26 (2009)
Guruswami, V., Sudan, M.: Improved decoding of Reed-Solomon and algebraic-geometric codes. IEEE Transactions on Information Theory 45, 1757–1767 (1999)
Høholdt, T., van Lint, J.H., Pellikaan, R.: Algebraic Geometry Codes. In: Pless, V.S., Huffamn, W.C., Brualdi, R.A. (eds.) Handbook of Coding Theory. Elsevier, Amsterdam (1998)
Kiayias, A., Yung, M.: Cryptographic hardness based on the decoding of Reed-Solomon codes. IEEE Transactions on Information Theory 54(6), 2752–2769 (2008)
Kulhandjian, M., Rudra, A., Pados, D.: Improved soft decoding of Reed-Solomon codes on Gilbert-Elliott channels (March 2010) (manuscript)
Kumar, S.R., Sivakumar, D.: Proofs, codes, and polynomial-time reducibilities. In: Proceedings of the 14th Annual IEEE Conference on Computation Complexity (1999)
MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes. Elsevier/North-Holland, Amsterdam (1981)
McEliece, R.J.: On the average list size for the Guruswami-Sudan decoder. In: 7th International Symposium on Communications Theory and Applications (ISCTA) (July 2003)
Parvaresh, F., Vardy, A.: Correcting errors beyond the Guruswami-Sudan radius in polynomial time. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 285–294 (2005)
Rudra, A.: List Decoding and Property Testing of Error Correcting Codes. Ph.D. thesis, University of Washington (2007)
Rudra, A.: Limits to list decoding random codes. In: Ngo, H.Q. (ed.) COCOON 2009. LNCS, vol. 5609, pp. 27–36. Springer, Heidelberg (2009)
Rudra, A., Uurtamo, S.: Datastream algorithms for codeword testing. In: Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP (to appear, 2010)
Rudra, A., Uurtamo, S.: Two theorems in list decoding. Technical Report TR10-007, Electronic Colloquium on Computational Complexity (January 2010)
Sudan, M.: Decoding of Reed-Solomon codes beyond the error-correction bound. Journal of Complexity 13(1), 180–193 (1997)
Sudan, M.: List decoding: Algorithms and applications. SIGACT News 31, 16–27 (2000)
Sudan, M.: Algorithmic introduction to coding theory (2001), lecture Notes available at http://people.csail.mit.edu/madhu/FT01/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rudra, A., Uurtamo, S. (2010). Two Theorems on List Decoding. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. RANDOM APPROX 2010 2010. Lecture Notes in Computer Science, vol 6302. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15369-3_52
Download citation
DOI: https://doi.org/10.1007/978-3-642-15369-3_52
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15368-6
Online ISBN: 978-3-642-15369-3
eBook Packages: Computer ScienceComputer Science (R0)