Monday, May 30, 2011
Deletion Channel Pointer : Kanoria and Montanari
For those half a dozen of us in the world who care about the deletion channel (and perhaps I'm overcounting), I'm a bit late in pointing to the now available extended version of the Kanoria and Montanari paper from ISIT last year. It follows a path laid out by my student Adam Kirsch by looking at an information theoretic characterization of the channel, but then uses a perturbation analysis to get the right degree distribution and very tight bounds as the deletion probability goes to 0. There's still plenty we don't understand about the deletion channel, but this paper moves us forward nicely.