Subexponential time run (Dagstuhl 10441)

Returning from the subexponential run wet and happy, from left to right: Mike Saks, Edward Hirsch, Paolo Codenotti, me, Mohan Paturi, and Marek Cygan. Photo by Hans Bodlaender.

I am spending the week at the Dagstuhl meeting 10441: Exact Complexity of NP-hard Problems, which I am also organising.

The site, Schloss Dagstuhl (Dagstuhl @ Wikipedia) is a wonderful place with lots of small details aimed at computer scientists. For example, the street address is Konrad Zuse-Straße. (A full list of Konrad Zuse-Straßen in Germany is maintained by his son, Horst Zuse.)

More whimsically, the marked running trial around Dagstuhl is called n2 [PDF]. As Dagstuhl attendees can attest, the route is pretty difficult despite its relatively short length of 5 kilometers. However, I felt that for a workshop on exponential time computation, polynomial “running times” are not ambitious enough, so I organised a longer run, based on the Bardenbacher-Fels-Weg (13–15 kilometers, depending on which map you consult). This hiking trail is currently labelled WA4 by the Wadern tourist authorities, but I am sure if I get the entire Max-Planck Gesellschaft behind me, I can get it renamed to exp(log2 n), or something similarly attractive.

In spite of a steady drizzle and the competition from attractive alternative hiking and biking outings, five attendees joined me on this, for a very satisfying run. Maybe next time we’ll arrange a half-marathon. Or maybe not.

Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s