Thursday, July 24, 2008

SWAT - Day 2

I wrote this entry about two weeks ago but haven't had a chance to post it. Better late than never...

Today's highlight was definitely the invited talk by Michael Mitzenmacher on deletion channels (his talk, and a survey, is available). Again a topic that I didn't know much about, but Michael's presentation gave me a good understanding of the basic problem and the questions that are important in this area. A deletion channel is a channel where n bits are sent, but each bit is independently deleted with fixed probability p. (Different from the erasure channel where each bit can be replaced by a `?', or the symmetric channel where each bit can be flipped). The main question is to decide the capacity of the channel. Michael showed that the lower bound (which is really an upper bound) is at least (1-p)/9. However, he also stated several interesting fundamental problems during his talk. For example, how do random subsequences of random sequences behave?

The conference dinner (I, & II) was held in a beautiful location just to the south of Gothenburg looking out on the archipelago. While the sun was setting we had good food and tried to come up with a new name for SWAT (I, II & III). The local organisers did a great job finding the place and arranging a historic tram trip to the venue.

No comments:

Post a Comment