77 papers made it in: I don't know how many were submitted (Update: 312, quite a healthy number). As is often with STOC, the titles are somewhat inscrutable, so it's hard to spot papers that might be interesting.
Some notable entries:
- Computing crossing number in linear time, by Ken-ichi Kawarabayashi and Bruce Reed:
For a fixed k, they determine whether a graph can be drawn with crossing number at most k, and if so, construct such a drawing, all in time linear in n. This improves an earlier quadratic time algorithm of Grohe.
- Combinatorial Complexity in o-Minimal Geometry, by Saugata Basu.
A continuation of his work on estimating complexity of various topological quantities, for even more generally defined subsets of Rn.
- Fourier meets Möbius: fast subset convolution, by Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto.
An application of the Möbius transform, in a kind of generalization of the use of Fourier transforms, but for subset convolutions.
- Lower Bounds for Randomized Read/Write Stream Algorithms, by Paul Beame, T. S. Jayram and Atri Rudra.
This is another in a series of papers that I really must read, given how it reminds me of things I was dabbling in involving graphics cards. The quirk of this model is that the stream algorithm can write onto streams as well as reading from them; memory is limited, but not intermediate storage (for writing such streams)