tag:blogger.com,1999:blog-3722233.post109503065115794074..comments2007-04-19T22:22:09.093-05:00Lancehttp://www.blogger.com/profile/06752030912874378610lance@fortnow.comBlogger4125tag:blogger.com,1999:blog-3722233.post-1095704344094564752004-09-20T13:19:04.096-05:002004-09-20T13:19:04.096-05:00I have seen mention in more than one place that this is beleived to be the best possible amount of error. I was wondering what evidence is there that one cannot do better. Is this just for RS codes or is it generally believed that the Johnson bound is tight for all codes?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1095625503761886062004-09-19T15:25:03.760-05:002004-09-19T15:25:03.760-05:00Now I see it... please ignore the last comment :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1095624651074358112004-09-19T15:10:51.073-05:002004-09-19T15:10:51.073-05:00Why is list-decoding necessary for the Sivakumar application? There the message has length n, and we look at a Reed-Solomon encoding of length q = poly(n) over a field of size q. Also for each index of the encoding we have a list of q^1/3 elements, which is guaranteed to include the right one. So if we guess each element at random from its list, we obtain a word that is, in expectation, within distance q^2/3 of the correct codeword. This is well within the unique decoding radius.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1095197976723247492004-09-14T16:39:36.723-05:002004-09-14T16:39:36.723-05:00Luca Trevisan also has a <A HREF="http://www.blogger.com/r?http%3A%2F%2Fwww.cs.berkeley.edu%2F%7Eluca%2Fpubs%2Fcodingsurvey.ps"> nice survey</A> on coding theory and its application to computational complexity.Anonymousnoreply@blogger.com