My usual pattern here is to start with high hopes of several long complicated blog posts, and then get more terse and less frequent as the conferences go on and I get more sleep-deprived. So don't count on this continuing...

This time, due to some snafu with the toll-free registration system, I'm staying at a non-conference hotel, and I'm happy with the choice. The room is nice, the internet is free, the place has character in a way that the Holiday Inn doesn't, the staff are very friendly, it's a pleasant ten-minute walk from the talks, it's noticeably cheaper, and they have a complimentary wine bar in the lobby in the evenings. The only flaw I've seen so far is that the neon sign advertising the place is dark in a few letters, so instead of the HOTEL CARLTON it calls itself the EL C LTON. Drop the C as well and you could be famous.

Erik Demaine, soon to be even more famous as a MoMA artist, is making a very strong start in the race for the best ratings of people to go to meals with. He used his fancy tiny computer's navigation software to lead us to a great hole-in-the-wall dim-sum place in Chinatown where we ate such foodstuffs as shrimp dumplings shaped like little bunny rabbits, with little food color eyes and all. They didn't scream when you bit their heads off, but they were yummy. Someone in the group suggested that the algorithm for ordering food at such places was to order \( 2n+2 \) items for \( n \) people (though we actually ordered more than that); we couldn't decide whether the \( +2 \) part of this formula really was a constant or whether some more complex function such as \( \log^* n \) was hiding there, but we eventually discovered what it was for when one more person joined our group after we were most of the way through and there was still plenty of food for him. Then, when the surprisingly small bill came, Erik surprised us again by picking the whole thing up himself, as a way to get rid of some cash he'd acquired smuggling illicit iPhones into Belgium. Thank you, Erik!

Since several people asked about it, my Math is delicious! Now with more integers! T-shirt can be found and purchased here.

Out this evening, we saw a pair of black high heeled shoes sitting, abandoned, on a window sill on Sutter Street. There must be a story there, I'm sure.

Talks? There were talks, too. Here's a random sample.

Frédéric Pluquet spoke (with very prettily typeset slides in what looked like Gill Sans, white on black with occasional splashes of red) on implementing persistent data structures, a paper with Stefan Langerman, Roel Wuyts, and Antoine Marot. Rather than forcing the implementor to actually think or work, he wants programmers to be able to simply say "make this data structure persistent" and make it work, much as the theory papers do — he put up a selection of quotes from some 20 papers that use persistence but only refer to it in a single line, one of which was my “visibility with a moving point of view”. To achieve this level of simplicity, he uses the fat node technique and aspect oriented programming, in a way that would likely work in any sufficiently introspective object-oriented language. The performance was a little disappointing, though: a factor of 40 slowdown in Java (not as bad in Smalltalk); this might still be ok, though, when a persistent data structure is a small part of a larger algorithm. On the way to lunch I discussed with Langerman the possibility of a Python implementation; he seemed to feel it shouldn't be harder than those other languages.

Don Knuth gave one of the two plenary talks, on what turned out to be three asymptotic enumeration type problems. The first was on the “medial Genocchi numbers”, a sequence closely related as the name implies to the (absolute values of the) Genocchi numbers studied by Euler. The two sequences of Genocchi numbers interleave to form a single sequence, where the even Genocchi number terms are approximated very well by a simple formula, \( 4(2n!)\pi^{-2n}\bigl(1+O(1/2^n)\bigr) \) if Erik and I deciphered Knuth's handwriting correctly, but the odd medial terms, while seeming to have the same leading term, have a much larger error term. Knuth wanted a more accurate approximation in that case. The second problem was on the distribution of the number of leaves of a uniformly random forest on \( n \) nodes after you strip off \( k \) levels of leaves and the paths leading to those leaves, and the third was on the asymptotics of a strange recurrence involving mins and sums that is related to the complexity of binary decision diagrams, with asymptotics that converge to a hairy monkey as you increase \( n \), but different monkeys for different sequences of the form \( n=4^i\times j \). The zeroth question (the one he decided at the last minute to omit from the talk, but was asked about afterwards) involved counting hypergraph analogues of forests, and was omitted after he did enough computation to find the appropriate sequences in OEIS. He referred to OEIS at several points in the talk, telling us in the end that this is the new way of doing science: compute your way to the right literature.

Daniel Dumitriu spoke on some work with Stefan Funke, Martin Kutz, and Nikola Milosavljevic on surface reconstruction. They have an approach which is based only on the distance matrix of the sample points: find a good subset of the points (an independent set of the \( k \)th power of the \( \kappa \)-nearest-neighbor graph), compute the graph Voronoi diagram, dualize it omitting some bad edges, and then greedily find cycles in order by length to use as faces. With some careful choice of parameters they can make most faces triangles, and prove guarantees on the quality of the reconstruction for three-dimensional samples similar to alternative techniques such as cocone.

Robert Geisberger spoke on approximating betweenness centrality in graphs. There was a known fast approximation based on finding single source shortest paths from a small set of pivot nodes, but although unbiased it tended to distort the centralities near the chosen pivots. Geisberger and his co-authors Peter Sanders and Dominik Schultes described how to compensate for that distortion while preserving the unbiased properties of the previous work. It seems likely that this should also be a good idea for closeness centrality, where I have a paper that (like the previous betweenness algorithm) is based on finding single source shortest paths from a small set of pivots.

Heidi Gebauer, after some technical difficulties with the projector-laptop connection, gave a nice presentation for her paper with Tibor Szabó and Emo Welzl related to a conjecture of mine. I had found a family of \( n \)-vertex cubic graphs with \( 2^{n/3} \) Hamiltonian cycles, and conjectured that no other cubic graphs have more, but the best upper bound I could prove was \( 2^{3n/8} \); she improves the upper bound. In some sense, her analysis should give a simple proof of a \( \varphi^{n/2} \) upper bound, where \( \varphi \) is the golden ratio, but a key lemma fails in some problematic cases; with more effort she was able to get most of the way to that bound anyway.

Tomorrow the main event starts. I can't play hooky, because I promised to chair two of the sessions...