Talk:List decoding

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
WikiProject Mathematics (Rated Start-class, Low-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Low Priority
 Field:  Discrete mathematics
WikiProject Computer science (Rated C-class, Low-importance)
WikiProject iconThis article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 Low  This article has been rated as Low-importance on the project's importance scale.
 

False Theorem[edit]

For fixed , is maximize for , but in the Sketch of proof section it is claimed that "The quantity gives a very good estimate on the volume of a Hamming ball of radius centered around any word in ". This can't be true, as this number is increasing in . As far as I can see, the Theorem only holds for . I guess it can be generalised to all , but the current generalisation seems to be wrong.

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


Hamming balls?[edit]

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)

What discipline? Which "community"?[edit]

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)