@inproceedings{cccc706cef4f47a1bc0d0afe02e2c630,

title = "H{\"o}lder homeomorphisms and approximate nearest neighbors",

abstract = " We study bi-H{\"o}lder homeomorphisms between the unit spheres of finite-dimensional normed spaces and use them to obtain better data structures for high-dimensional Approximate Near Neighbor search (ANN) in general normed spaces. Our main structural result is a finite-dimensional quantitative version of the following theorem of Daher (1993) and Kalton (unpublished). Every d-dimensional normed space X admits a small perturbation Y such that there is a bi-H{\"o}lder homeomorphism with good parameters between the unit spheres of Y and Z, where Z is a space that is close to ℓ d 2 . Furthermore, the bulk of this article is devoted to obtaining an algorithm to compute the above homeomorphism in time polynomial in d. Along the way, we show how to compute efficiently the norm of a given vector in a space obtained by the complex interpolation between two normed spaces. We demonstrate that, despite being much weaker than bi-Lipschitz embeddings, such homeomorphisms can be efficiently utilized for the ANN problem. Specifically, we give two new data structures for ANN over a general d-dimensional normed space, which for the first time achieve approximation d o(1) , thus improving upon the previous general bound O(√d) that is directly implied by John's theorem. ",

keywords = "Complex interpolation, John's theorem, Near neighbor search",

author = "Alexandr Andoni and Assaf Naor and Aleksandar Nikolov and Ilya Razenshteyn and Erik Waingarten",

year = "2018",

month = nov,

day = "30",

doi = "10.1109/FOCS.2018.00024",

language = "English (US)",

series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

publisher = "IEEE Computer Society",

pages = "159--169",

editor = "Mikkel Thorup",

booktitle = "Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018",

address = "United States",

note = "59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 ; Conference date: 07-10-2018 Through 09-10-2018",

}