Tuesday, June 2, 2009

STOC

Other folks already have some nice STOC summaries up (Bill/Lance, Michael), so I won't repeat them except to say that not only was Shafi Goldwasser's Athena Lecture excellent, her jokes were intelligent too (if you missed it, it looks like there might be a video posted here some day). Truly a talk worth seeing.

Another talk that's gotten less attention, but that I thought was exciting, was the paper "Homology flows, cohomology cuts" by Erin Chambers, Jeff Erickson, and Amir Nayyeri. There's no point paraphrasing when they say it so well themselves:



We describe the first algorithms to compute Maximum flows in surface-embedded graphs in near-linear time. Given an undirected graph embedded on an orientable surface of genus g, with two specified vertices s and t, our algorithm computes a maximum (s,t)-flow in in O(g7 n log2n log2C) time for integer capacities that sum to C, or in (g log n)O(g) n time for real capacities. Except for the special case of planar graphs, for which an O(n log n)-time algorithm has been known for 20 years, the best previous time bounds for maximum flows in surface-embedded graphs follow from algorithms for general sparse graphs. Our key insight is to optimize the relative homology class of the flow, rather than directly optimizing the flow itself. A dual formulation of our algorithm computes the minimum-cost cycle or circulation in a given (real or integer) homology class.

Check out their full paper from Jeff's site, where I also stole the nice graphic and abstract from.

I was volunteering for the conference (Maryland was the local host) and spent some of my time working the registration desk, which gave me a nice chance to see people as they entered. It was nice to meet some of you in person. Even though the business meeting was a bit tame (perhaps Chazelle should be given best paper awards at every conference to add entertainment value...), it seems to have been a successful conference. Congrats and thanks to all the organizers/speakers/PC members/etc.

No comments: