Monday, January 30, 2006

STOC 2006 results out

List of papers here.

Some quick notes on seeing the papers:
More to (hopefully) come as I peruse the list.

Update: 1/31/06: Sariel points out two more interesting papers:
  • Searching Dynamic Point Sets in Spaces with Bounded Doubling Dimension - Richard Cole and Lee-Ad Gottlieb.
  • A Quasi-Polynomial Time Approximation Scheme for Minimum Weight Triangulation - Jan Remy and Angelika Steger.

    This one is particularly interesting in the light of the new NP-hardness result for MWT by Mulzer and Rote. A quick glance at the above paper indicates that they use a technique akin to the method used by Sanjeev Arora, and Joe Mitchell, to solve TSP in the plane. You divide the plane into small pieces, consider the different triangulations in each piece, and prove a "structure lemma" that describes how the interface of almost-optimal solutions look. Since the algorithm runs in quasi-polynomial time, I imagine the next step is to see if it can be be beaten down to a PTAS.
Credit goes where credit is due. The geometry community often moans and groans about their neglect at the hand of STOC/FOCS committees. This time, there is really nothing to complain about; a lot of nice geometry papers have made it in.

Disqus for The Geomblog