Dagstuhl...

I had decided not to post anything from here, because after all, from a technical perspective, most of the people who'd be interested in the work are already here ! But then again, ...

The workshop is on sublinear algorithms, algorithms that use a sublinear amount of some resource (space or time). Sublinear time algorithms might seem odd, but they come under the general rubric of property testing, where the idea is that by probing an input in a small number of places, you can learn something about it. Property testing shows up in many places; indeed the PCP theorem itself can be viewed as a kind of property testing algorithm, where the object is the "proof" of membership, and a few (randomized) queries are made to check its correctness.

Sublinear space algorithms are of course stream algorithms, something that I've talked about before.

What is interesting (to me) is the amount of work in testing properties of distributions. For example, can I tell if a distribution is uniform with only a few samples ? Can I tell if it is the joint distribution of two independent variables ? Can I compute its entropy ?


In other matters, ...

The one think I like best is the randomized seat assignments. Lunch and dinner seating is fixed, and changes each meal. So not only is the tension of "where should I sit today" reduced, one gets to meet and chat with different folks each time.

Another is the size of the tables; at most of our conferences, the tables are big enough that disconnected conversation cliques form, which is really no fun. Here, the tables are small and seat only 5 people: you really have to have everyone involved in the conversation.

Talks are chugging along: lots more than one might think for an informal workshop. Thankfully mine is done, though I can't say I was very happy with it.