A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube
From MaRDI portal
Publication:2819559
DOI10.1145/301250.301325zbMath1346.68078OpenAlexW2001964584MaRDI QIDQ2819559
Amit Chakrabarti, Benjamin Gum, Alexey Lvov, Bernard Chazelle
Publication date: 29 September 2016
Published in: Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/301250.301325
Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
A strong lower bound for approximate nearest neighbor searching ⋮ The cell probe complexity of succinct data structures ⋮ Tighter lower bounds for nearest neighbor search and related problems in the cell probe model ⋮ Cell-probe lower bounds for the partial match problem ⋮ Computing (and Life) Is All about Tradeoffs ⋮ Optimal bounds for the predecessor problem and related problems
