Aarhus University Seal

Lower Bounds for Oblivious Near-Neighbor Search

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review


  • Kasper Green Larsen
  • Tal Malkin, Columbia University, Denmark
  • Omri Weinstein, Columbia University
  • ,
  • Kevin Yeo, Columbia University, Google LLC

We prove an Ω(dlg n/(lg lg n) 2) lower bound on the dynamic cell-probe complexity of statistically oblivious approximate-near-neighbor search (ANN) over the ddimensional Hamming cube. For the natural setting of d = Θ(lg n), our result implies an Ω(lg 2 n) lower bound, which is a quadratic improvement over the highest (non-oblivious) cell-probe lower bound for ANN. This is the first super-logarithmic unconditional lower bound for ANN against general (non black-box) data structures. We also show that any oblivious static data structure for decomposable search problems (like ANN) can be obliviously dynamized with O(lg n) overhead in update and query time, strengthening a classic result of Bentley and Saxe (Algorithmica, 1980).

Original languageEnglish
Title of host publicationSODA '20: Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms
EditorsShuchi Chawla
Number of pages19
Place of publicationPhiladelphia
PublisherSociety for Industrial and Applied Mathematics
Publication year2020
ISBN (Electronic)9781611975994
Publication statusPublished - 2020
Event31st ACM-SIAM Symposium on Discrete Algorithms - Hilton Salt Lake City Center, Salt Lake City, United States
Duration: 5 Jan 20208 Jan 2020


Conference31st ACM-SIAM Symposium on Discrete Algorithms
LocationHilton Salt Lake City Center
LandUnited States
BySalt Lake City

See relations at Aarhus University Citationformats

ID: 170313374