A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube.

Amit Chakrabarti, Bernard Chazelle, Benjamin Gum, Alexey Lvov

Browse the full STOC paper archive.