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.

Sunday, July 13, 2008

SWAT - Day 1

A bit late but here's a short summary of SWAT day 1:

I'm in Gothenburg attending SWAT 2008. I haven't been in Gothenburg since I was a kid but it's a beautiful city this time of the year. Due to the long and warm summer evening there are heaps of people everywhere. Apart from SWAT there's also the worlds largest youth handball tournament going on with 900 teams from all around the world.

The local organisers of SWAT seem to have everything under control. I don't have to worry about anything (except a nasty cold). The first day included some very nice talks. John Hershberger gave the first talk of the conference, "Simplified planar coresets for data streams" which gives a simple way of producing coresets for computing the extent of a point set in the plane. He (and Subhash Suri) combined several known techniques with a few nice ideas to obtain an optimal size coreset.
Another talk I enjoyed was on placing wireless devices in an internet cafe such that customers inside the cafe can be distinguished from people outside the cafe. The talk was given by Tobias Christ and they show that for a simple polygon with n vertices 3n/5 devices is sometimes necessary and that 4n/5 is always sufficient.

Vijay Vazirani gave a great invited talk on the relation between Nash bargaining and flexible markets. I don't know the area very well but Vijay gave a very good survey focussing on the fact that some of these problems can be stated as a convex program which can be shown to have a rational optimal solution which can be solved in polynomial time by using primal-dual techniques.

After the technical program there was a business meeting where various issues were discussed (more on that in an upcoming post), followed by a reception at the city hall (provided by the city of Gothenburg) and the PC dinner (for details of what was discussed see Michael's post).

Friday, July 11, 2008

postdoc positions in USyd

University of Sydney is inviting applications for postdoc fellowships in any department/research area. The closing date for applications is september 12. if i'm reading the information on the web correctly, these postdoc fellowships provide a salary of about 70K, 25K research funding, some relocation expenses and have a max duration of 3 years.