Maybe I am reading too much into titles, but it seems like hardness results are back in business again. From a highly unprofessional inspection of the FOCS list:
An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching
Hardness of Approximating the Shortest Vector Problem in Lattices
Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique
On the (Im)possibility of Cryptography with Imperfect Randomness
The Hardness of Metric Labeling
Hardness of buy-at-bulk network design
Optimal Inapproximability Results for MAX-CUT and Other 2-variable CSPs?
If I get a chance I will comment on some of the interesting geometry papers out there (have been pinging authors for copies).
Yes, there have been a spate of hardness of approximation results in the last two years.
ReplyDeleteThis is good news - eliminates lot of problems
that people have been trying to design improved
approximation algorithms for and have failed.
Metric labeling and buy-at-bulk come to mind.
Chandra