Talk:List decoding

For fixed ${\displaystyle q}$ , ${\displaystyle H_{q}($p)=-p\log _{q}(p)-(1-p)\log _{q}(1-p)}   is maximize for ${\displaystyle p=1/2}$ , but in the Sketch of proof section it is claimed that "The quantity ${\displaystyle q^{H_{q}($p)}}   gives a very good estimate on the volume of a Hamming ball of radius ${\displaystyle p}$  centered around any word in ${\displaystyle [$q]^{n}}  ". This can't be true, as this number is increasing in ${\displaystyle p}$ . As far as I can see, the Theorem only holds for ${\displaystyle q=2}$ . I guess it can be generalised to all ${\displaystyle q>2}$ , but the current generalisation seems to be wrong.

--31.54.122.93 (talk) 14:04, 22 March 2014 (UTC)Reply

The article has a lot of information related to Hamming balls. Except their definition... 134.58.42.46 (talk) 09:10, 9 November 2010 (UTC)Reply

This article begins with representing coding theory as part of computer science ("In computer science, particularly in coding theory..."). I think this is somewhat misleading; coding theory is at the intersection of several major disciplines. Mathematics and electrical engineering have at least as much claim on coding theory as does computer science. I suggest to say "In mathematics, computer science, and electrical engineering, particularly in coding theory..."

The article mentions several times the significant algorithmic progress "by the coding theory community." This designation of the community responsible for the recent progress on list decoding is in a way a tautology (whoever makes significant progress on coding theory is a member of the coding theory community by definition); in another way it is a serious misrepresentation. The community that made this progress is very clearly identifiable: it is the theory of computing (theoretical computer science) community; and more specifically, the computational complexity theory community. The central problems and paradigms of computational complexity theory (such as probabilistically checkable proofs), rather than those of information theory, have driven the agenda that resulted in these major contributions to information theory. It would therefore be far more informative to talk about significant algorithmic progress "by the computational complexity theory community." It is a remarkable fact of the development of the sciences how one area impacts another, and this example deserves highlighting. Prior to this invasion of coding theory by the computational complexity theory community, the central paradigms of complexity theory (asymptotic thinking, rates of growth, "polynomial time," etc.) received very little attention in the "coding theory community." --Lbabai (talk) 07:57, 19 December 2012 (UTC)Reply