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.


Andy D said...

Looks very interesting.

Thinking out loud... has anyone rigorously studied channel models in which symbols may arrive slightly out of order?

There are several ways this could be modeled. One is to stipulate that the transmission time of each symbol follows an exponential distribution (independent from the rest). One might learn the arrival times, or just the time-ordered sequence of arrived symbols.

Michael Mitzenmacher said...

Andy D -- interesting suggestion. Some poking around led me to this interesting and very new-ish paper, suggesting there's some interesting questions with this sort of model.