Kevin
Yeo
Google
Research
We prove an Ω(dlgn/(lglgn)^2) lower bound on the dynamic cell-probe complexity of statistically oblivious approximate-near-neighbor search (ANN) over the d-dimensional Hamming cube. For the natural setting of d=Θ(lgn), 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(lgn) overhead in update and query time, strengthening a classic result of Bentley and Saxe (Algorithmica, 1980).
Joint work with Kasper Green Larsen, Tal Malkin and Omri Weinstein.