Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems.

Allan Borodin, Rafail Ostrovsky, Yuval Rabani

Browse the full STOC paper archive.