Abstract
It has been known since [Zyablov and Pinsker 1982] that a random q-ary code of rate 1 − H q (ρ) − ε (where 0 < ρ< 1 − 1/q, ε> 0 and H q (·) is the q-ary entropy function) with high probability is a (ρ,1/ε)-list decodable code. (That is, every Hamming ball of radius at most ρn has at most 1/ε codewords in it.) In this paper we prove the “converse” result. In particular, we prove that for every 0 < ρ< 1 − 1/q, a random code of rate 1 − H q (ρ) − ε, with high probability, is not a (ρ,L)-list decodable code for any, where c is a constant that depends only on ρ and q. We also prove a similar lower bound for random linear codes.
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
Blinovsky, V.M.: Bounds for codes in the case of list decoding of finite volume. Problems of Information Transmission 22(1), 7–19 (1986)
Elias, P.: List decoding for noisy channels. Technical Report 335, Research Laboratory of Electronics, MIT (1957)
Gilbert, E.N.: A comparison of signalling alphabets. Bell System Technical Journal 31, 504–522 (1952)
Guruswami, V.: List Decoding of Error-Correcting Codes. LNCS, vol. 3282. Springer, Heidelberg (2004)
Guruswami, V.: Algorithmic Results in List Decoding. Foundations and Trends in Theoretical Computer Science (FnT-TCS), NOW publishers 2(2) (2007)
Guruswami, V., Vadhan, S.P.: A lower bound on list size for list decoding. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol. 3624, pp. 318–329. Springer, Heidelberg (2005)
Hamming, R.W.: Error Detecting and Error Correcting Codes. Bell System Technical Journal 29, 147–160 (1950)
MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes. Elsevier/North-Holland, Amsterdam (1981)
Rudra, A.: List Decoding and Property Testing of Error Correcting Codes. PhD thesis, University of Washington (2007)
Rudra, A.: Limits to list decoding random codes. Electronic Colloquium on Computational Complexity (ECCC) 16(013) (2009)
Shannon, C.E.: A mathematical theory of communication. Bell System Technical Journal 27, 379–423, 623–656 (1948)
Sudan, M.: List decoding: Algorithms and applications. SIGACT News 31, 16–27 (2000)
Varshamov, R.R.: Estimate of the number of signals in error correcting codes. Doklady Akadamii Nauk 117, 739–741 (1957)
Wozencraft, J.M.: List Decoding. Quarterly Progress Report, Research Laboratory of Electronics, MIT 48, 90–95 (1958)
Zyablov, V.V., Pinsker, M.S.: List cascade decoding. Problems of Information Transmission 17(4), 29–34 (1981) (in Russian); 236–240 (1982) (in English)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rudra, A. (2009). Limits to List Decoding Random Codes. In: Ngo, H.Q. (eds) Computing and Combinatorics. COCOON 2009. Lecture Notes in Computer Science, vol 5609. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02882-3_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-02882-3_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-02881-6
Online ISBN: 978-3-642-02882-3
eBook Packages: Computer ScienceComputer Science (R0)