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

Disqus for The Geomblog