### Abstract

We study bi-Hö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ö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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 |

Editors | Mikkel Thorup |

Publisher | IEEE Computer Society |

Pages | 159-169 |

Number of pages | 11 |

ISBN (Electronic) | 9781538642306 |

DOIs | |

State | Published - Nov 30 2018 |

Event | 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 - Paris, France Duration: Oct 7 2018 → Oct 9 2018 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

Volume | 2018-October |

ISSN (Print) | 0272-5428 |

### Other

Other | 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 |
---|---|

Country | France |

City | Paris |

Period | 10/7/18 → 10/9/18 |

### All Science Journal Classification (ASJC) codes

- Computer Science(all)

### Keywords

- Complex interpolation
- John's theorem
- Near neighbor search

## Fingerprint Dive into the research topics of 'Hölder homeomorphisms and approximate nearest neighbors'. Together they form a unique fingerprint.

## Cite this

*Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018*(pp. 159-169). [8555102] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2018-October). IEEE Computer Society. https://doi.org/10.1109/FOCS.2018.00024