Some quick notes on seeing the papers:
- The PCP Theorem via Gap Amplification - Irit Dinur: Probably one of the most discussed papers of the year...
- Building triangulations with epsilon-nets - Kenneth L. Clarkson. A paper I greatly enjoyed reading, and brings some nice differential geometry into the area of meshing and surface approximation in general.
- On the Importance of Idempotence - S. A. Arya and T. Malamatos and D. M. Mount. I heard David Mount talk about this at the Fall Workshop: it's a very delicate paper that shows how the kind of semigroup used in exact and approximate range searching can make a big difference in the bounds that are proved.
- Approximate Nearest Neighbors and the Fast Johnson-Lindenstrauss Transform - Nir Ailon and Bernard Chazelle. I haven't read this yet, but Jeff's already seen the slides.!
- A Randomized Polynomial-Time Simplex Algorithm for Linear Programming - Jonathan A. Kelner and Daniel A. Spielman. and
- Explicit Capacity-Achieving List-Decodable Codes - Venkatesan Guruswami and Atri Rudra: both of these being Lance's Christmas theory presents.
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.
I would add to the list:
ReplyDelete- 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
Ahhh. I was looking for the MWT paper. I had heard something about it. Thanks for the pointers.
ReplyDeletePosted by Suresh
There are two MWT papers. This is a (1+epsilon) approximation; the other one (not submitted to STOC) is the NP-completeness proof.
ReplyDelete