Hardness of approximate nearest neighbor search

DOI10.1145/3188745.3188916zbMath1428.68167arXiv1803.00904OpenAlexW2963964051MaRDI QIDQ5230379

Aviad Rubinstein

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1803.00904

zbMATH Keywords

nearest neighbor searchalgebraic-geometry codefine-grained complexitydistributed PCP

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

On the Complexity of Closest Pair via Polar-Pair of Point-Sets ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On closest pair in Euclidean metric: monochromatic is as hard as bichromatic ⋮ ForestDSH: a universal hash design for discrete probability distributions ⋮ Index structures for fast similarity search for symbol strings ⋮ On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic ⋮ On the Complexity of Closest Pair via Polar-Pair of Point-Sets ⋮ Fine-grained complexity theory: conditional lower bounds for computational geometry