Continuing my efforts to prove I was not just sitting out by the pool in New Zealand, I'll mention a highlight of the talks of Brendan McKay (of the Australian National University). Brendan has written code for graph isomorphism called nauty that works quite well in practice, handling graphs with up to millions of nodes. So while the complexity of the graph isomorphism problem is not known, it can be pretty hard to come up with bad examples that are actually hard to solve. As someone who's happy with good heuristics, I found it quite amusing to watch it in action. (On the other hand, it seems that many of the ideas behind this program are "old" by computer science standards. Are there any competing programs/approaches out there? Seems like a possible research direction. to revisit the algorithm engineering for this problem...)
While settling whether graph isomorphism is in P would certainly be interesting, Brendan pointed out that the question of whether it is in coNP is also quite important. Are there polynomial-sized certificates that can be used to prove that two graphs are not isomorphic? And one can imagine in practice one would like to have some methodology for easily convincing someone that two graphs aren't isomorphic.
As Brendan is a co-editor-in-chief of the Electronic Journal of Combinatorics, we also talked a bit at lunch about electronic journals (in particular the EJC). The EJC continues to grow successfully. (I'm happy to say I've published in it, back in 2004.) Remember to support your electronic journals.