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.


  1. I would add to the list:
    - Searching Dynamic Point Sets in Spaces with Bounded Doubling Dimension.
    Richard Cole and Lee-Ad Gottlieb
    They show how to maintain ANN dynamically in low doubling dimension spaces. Not a simple result, but still nice.

    - A Quasi-Polynomial Time Approximation Scheme for Minimum Weight Triangulation,
    Jan Remy and Angelika Steger.
    If this is what the title claims, that this is an interesting result, especially considering the SoCG submission showing the problem is npc.

    Somewhat surprisingly, Vladlen result did not get in. Overall a lot of geometry papers for STOC.

    Posted by Sariel

  2. Ahhh. I was looking for the MWT paper. I had heard something about it. Thanks for the pointers.  

    Posted by Suresh

  3. There are two MWT papers. This is a (1+epsilon) approximation; the other one (not submitted to STOC) is the NP-completeness proof.

  4. There's also "The distance trisector curve " by Asano, Matousek, and Tokuyama, which gets my vote for the "Least Likely Geometry Paper To Be Submitted, Never Mind Accepted, To STOC" award. It's a very cool paper, but still....


Disqus for The Geomblog