tag:blogger.com,1999:blog-3722233.post113067670512836290..comments2020-02-16T18:25:33.023-05:00Comments on Computational Complexity: List Decoding Beyond ExpectationsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-1130891307118602142005-11-01T19:28:00.000-05:002005-11-01T19:28:00.000-05:00This was asked last time, but never answered: what...This was asked last time, but never answered: what is the evidence that Guruswami and Sudan's algorithm is likely the best possible for the Reed-Solomon code?<BR/><BR/>It is not clear if there is any "compelling" evidence. Beyond the radius decoded by their algorithm, we do not know if there will always only be a polynomial number of codewords to output (which is a guarantee we need to be able to decode in polynomial time). It is possible this number shoots to super-polynomial just beyond this radius --- some works have explored this possibility, though the question remains wide open. It could also be that the choice of evaluation points used for the Reed-Solomon encoding matters, and that for a clever choice one could decode from many more errors.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1130732130133818952005-10-30T23:15:00.000-05:002005-10-30T23:15:00.000-05:00Wow, that is a significant result!Any idea what th...Wow, that is a significant result!<BR/><BR/>Any idea what the patent status of this new algorithm will be?<BR/><BR/>Is that rate the information-theoretic limit? (I suspect that it is, but don't know the appropriate approximations for factorials offhand.)<BR/><BR/>Any idea if it will be possible to apply techniques which use the fact that errors tend to be next to each other in the real world to this approach?<BR/><BR/>Does this technique require a lot of random access, or can it do a decent job of avoiding cache misses and disk seeks as well?<BR/><BR/>It's good to see some theory making practical contributions, a little surprising that the most exciting stuff is information theoretic right now though.Bram Cohennoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1130723351304483112005-10-30T20:49:00.000-05:002005-10-30T20:49:00.000-05:00This was asked last time, but never answered: what...This was asked last time, but never answered: what is the evidence that Guruswami and Sudan's algorithm is likely the best possible for the Reed-Solomon code?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1130719810814692282005-10-30T19:50:00.000-05:002005-10-30T19:50:00.000-05:00I should have said a "1-ε" fract...I should have said a "1-ε" fraction of errors, i.e., for a code of length m, all but εm entries can be corrupted, where entries are elements of some finite field. The rate refers to the throughput: If a code of length m encodes an input of length n (with the same alphabet) then the rate is n/m.Lancehttps://www.blogger.com/profile/10719117059849994105noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1130708579519910482005-10-30T16:42:00.000-05:002005-10-30T16:42:00.000-05:00Perhaps I just don't understand the terminology - ...Perhaps I just don't understand the terminology - what does 1-e errors mean? What is meant by 'rate'? 1-e obviously doesn't refer to an absolute number, does it meant that an e proportion of all values are altered or that a 1-e proportion of all values are altered? Is 'rate' a time-based measure or an amount of error correcting code measure?Bramnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1130694713203854232005-10-30T12:51:00.000-05:002005-10-30T12:51:00.000-05:00It's \epsilon on my screen, bram. Font problem, pr...It's \epsilon on my screen, bram. Font problem, probably (unless something really strange is happening her).<BR/>GiladAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1130689843297753722005-10-30T11:30:00.000-05:002005-10-30T11:30:00.000-05:00Isn't log(1/e) a negative number? It doesn't appea...Isn't log(1/e) a negative number? It doesn't appear that e is 'epsilon', because the other function is e*e.Bramnoreply@blogger.com