STOC 2007 Results out

Via Piotr, the STOC 2007 results are out. They are sneakily hidden on Uri Feige's home page, so if you go to the STOC page, you don't see them.

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 Rⁿ.

• 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)

Parochial concerns section: by my count, 6 geometry papers, which is fairly decent.