Tuesday, June 29, 2004

Lower bounds comeback ?

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

1 comment:

  1. Yes, there have been a spate of hardness of approximation results in the last two years.
    This 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

    ReplyDelete

Disqus for The Geomblog