The Big Easy

I'm in New Orleans for SODA, at the same time as thousands of mathematicians have converged on the area for an AMS meeting. My flight was delayed, so by the time I arrived yesterday the hotel check-in clerk told me there were no internet rooms available and I'd have to change rooms the next day if I wanted that. Imagine my pleasant surprise when the ethernet plug in the room she gave me worked anyway!

As for the talks, Suresh has given a good description of Flajolet's plenary talk, about going from descriptions of combinatorial objects to formulas for their generating functions automatically without any intermediate recurrences, and the strong average case analysis results obtainable by such methods.

I also enjoyed Erik Demaine's talk, on partitioning the edges of graphs on low-genus surfaces into subsets such that contracting any subset produces bounded treewidth, despite Erik embarrassing me in the middle of the talk for holding my program up to my face. Good thing it wasn't something about auctions or I'm sure I would have had to walk away with an expensive purchase... A quick example to illustrate the concept, although it has little to do with how Erik constructs these partitions: consider a tiling of the plane into equilateral triangles, and partition the edges into three classes by their slopes. Then contracting all the edges in any one class would collapse the whole triangulation into a single line, giving a very low treewidth graph. By constructing such a partition for an input graph, and trying each possible way to collapse it, one can find good approximations for many graph optimization problems including the TSP for bounded genus graphs.

I think the talk that led me to think the most, though I'm not sure that's a complement (it means I wasn't paying as much attention as I should have) was Nir Ailon's, on aggregation of partial rankings. That is, not unlike a conference program committee meeting, several people give partial rank orderings of the same set of objects and you have to form a single ranking from them all. What he means by a "partial ranking" is just a weak order or total preorder; that is, a partition of the items into equivalence classes together with a total ordering on the equivalence classes. What one would need to handle the program committee meeting problem would be a weaker notion of ordering, in which PC members are allowed to omit some of the elements from their rankings; that is, it should be a total preorder on a subset of the elements. What I was thinking about during Ailon's talk was how to characterize these things using forbidden suborders. A strict weak order is a partial order in which there are no three elements \(\{a,b,c\}\) having the order \(\{a \lt b\}\), and it seems that a weak ordering with omitted elements should be the same as a partial order in which there are no four elements \(\{a,b,c,d\}\) having one of four forbidden orders \(\{a \lt b,c \lt d\}\), \(\{a \lt b,a \lt d,c \lt d\}\), \(\{a \lt b,b \lt c,a \lt c,a \lt d\}\), \(\{a \lt b,b \lt d,a \lt d,c \lt d\}\). But the weak orders form a medium while I don't think that's true of weak orders with omitted elements.

Bourbon Street is if anything louder and more of a parody of itself than it was the last time I was here, whenever SODA was here last. The places with some aspirations to tastefulness such as the Two Sisters and Preservation Hall are closed (or were tonight, anyway), while the bars, clubs, and strip joints seem to be thriving. If that's what most of the visitors here want, though, I don't see why that shouldn't be what they get.

Comments: