ALENEX

So ALENEX started and ended today. The workshop started off with a keynote address by Bernard Moret on the Tree of Life and algorithmic issues in phylogeny. He set out an impressively complex landscape of problems, most of which required some serious algorithm engineering (fitting for ALENEX). One quote that I found rather amusing:

Truth is not part of the vocabulary of algorithm design

This was when discussing how the goal of algorithms (optimization) differs from the goal of biology (scientific truth).

Later on, at the business meeting, we had the customary discussion of mindless statistics (how many papers were written by left-handed dwarfs from the eastern provinces of Transylvania ?). 15/60 papers were accepted, which is an impressive acceptance ratio. The submission rate appears to be relatively stable, and 15 is the maximum number of papers that can fit in a one-day workshop. Another mildly interesting stat was the fraction of papers submitted from Europe - 44.6%. This (to me) appears to be quite high, especially given that the workshop is in the West Coast.

Cathy McGeoch brought out a beautiful poster representing the history of NP-Completeness. It has a top section describing NP-hardness and complexity, and the main area of the poster is taken up by a graph in which vertices are NP-hard problems and edges are reductions. The nodes are colored by their Garey+Johnson classification, and immediately you see how SAT pops out as the source problem of choice for so many reductions.

The poster is being sold for $120 + $15 shipping (it's at least 36'' X 48''), and was designed by an ex-Amherst faculty member who now runs a graphic design company. No web pictures or thumbnails as of yet: I'll update this post when they appear. If you want to order a poster, send mail to Cathy [ ccm at cs dot REMOVEamherstTHIS dot edu ]. [Update: Click here for the poster website and a nifty Flash tool to navigate the poster.]

One of the motivations that Cathy mentioned was the lack of computer science art. It would be cool if we could create a poster for Chad Brewbaker's Complexity Zoo map.

In later postings I will mention some of the talks that I found interesting. I've been blogging from conferences for a while now, and I notice that I often feel the pressure to say something about every paper, for fear that by exclusion, I am making a statement about a talk/paper. Rest assured that this is not the case.

In related news, Lance inspires yet another theorist to start a blog. He is indeed the Blogfather of theory :).