ESA 2009

ESA is being held at the IT University of Copenhagen. It's a wonderful, fairly new university building, with one strange problem -- a severe shortage of plug outlets. Really, it's like a scavenger hunt to find one. The auditorium has just a couple of outlets oddly placed in the way back -- a far cry from the plug at every desk I'm used to in many newer academic buildings. I guess they don't want people plugged in during big talks here.

ESA is unusual in that it has an Engineering and Applications Track, so you actually see some papers with graphs and numerical results from implementations. I only point this out because I almost collapsed in shock when leafing through the papers I saw some actual performance plots (in algorithms papers????), but then recalled this feature of ESA.

I think there's something at ESA for everyone; sadly, I'm flying back and missing a number of the talks of papers I'd like to see, including some hash-based data structure talks:

Rina Panigrahy and Eric Lehman. 3.5-Way Cuckoo Hashing for the Price of 2
Johannes B Hreinsson, Morten Krøyer and Rasmus Pagh. Storing a Compressed Function with Constant Time Access
Martin Aumüller, Martin Dietzfelbinger and Michael Rink. Experimental variations of a theoretically good retrieval data structure

A paper outside my usual scope that caught my eye:

Erik D. Demaine, MohammadTaghi Hajiaghayi and Dániel Marx. Minimizing Movement: Fixed-Parameter Tractability

Fixed-parameter tractability seems like a great direction for getting efficient algorithms for hard problems; the paper reminds me that I could see adding a lecture on it to my undergraduate algorithms class.

The title that got my attention most was:

Andrew McGregor, Krzysztof Onak and Rina Panigrahy. The Oil Searching Problem

I just wanted to know what the oil searching problem was from the title. It's a competitive ratio/exploration problem generalizing the standard cow-path problem: you've got n wells, each with oil at a different depth, how do you drill to find oil with as little drilling as possible. As the authors point out, this can model research -- you've got n problems that will require different unknown amounts of work to solve....

Award-winning papers are:
Best student paper : Heidi Gebauer. Disproof of the Neighborhood Conjecture with Implications to SAT
Best paper: Christoph Dürr, Flavio Guiñez and Martín Matamala. Reconstructing 3-colored grids from horizontal and vertical projections is NP-hard

Before heading to the airport, I got to see Erik Demaine's talk on Algorithms Meet Art, Puzzles, and Magic. It's an interesting and entertaining talk, though I wish he had a little more time at the end. I recommend it if it comes to a town near you.

On the plus side, ESA still gives out a hefty LNCS paper book, so I'll be able to read about what I miss on the way home, at the cost of dragging some extra heft around various airports.