The best paper award for track A went to the paper The complexity of Boolean formula minimization by David Buchfuhrer and Christopher Umans. The best student paper for track A was given to Jeff Phillips for his paper Algorithms for epsilon-approximations of Terrains.
The awards for track B were made to the papers
- Mai Gehrke, Serge Grigorieff and Jean-Eric Pin. Duality and equational theory of regular languages (best paper) and
- Christian Mathissen. Weighted Logics for Nested Words and Algebraic Formal Power Series (best student paper).
There is a lot more to report from the conference, but time is short right now. Let me just point out that today ICALP 2008 featured a very special event, which was attended by about 300 participants, including the Icelandic Math Olympiad team, high school teachers of mathematics and members of the public at large. Peter Winkler (Dartmouth, USA) delivered a truly outstanding master class on mathematical puzzles entitled Puzzles You Think You Must Not Have Heard Correctly. It is the first time that ICALP features this type of event bringing a TCS conference of this calibre to a wider audience. Anna, Magnús and I are very happy to see how well it all went. Thanks to Peter for a truly inspirational talk!
When Peter presented the "Boxes in Boxes" puzzle, he said that
Magnús remarked that this is definitely true in Iceland for all train stations here. This is an example of logic at its best, and I'll use it next time I have to teach universal quantification over an empty set :-)
At many train stations, post offices and currier services around the world, the cost of sending a
rectangular box is determined by the sum of its dimensions; that is, length plus width plus height.