Welcome to the resource topic for 2019/377
Title:
Lower Bounds for Oblivious Near-Neighbor Search
Authors: Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo
Abstract:We prove an \Omega(d \lg n/ (\lg\lg n)^2) lower bound on the dynamic cell-probe complexity of statistically \mathit{oblivious} approximate-near-neighbor search (\mathsf{ANN}) over the d-dimensional Hamming cube. For the natural setting of d = \Theta(\log n), our result implies an \tilde{\Omega}(\lg^2 n) lower bound, which is a quadratic improvement over the highest (non-oblivious) cell-probe lower bound for \mathsf{ANN}. This is the first super-logarithmic \mathit{unconditional} lower bound for \mathsf{ANN} against general (non black-box) data structures. We also show that any oblivious \mathit{static} data structure for decomposable search problems (like \mathsf{ANN}) can be obliviously dynamized with O(\log n) overhead in update and query time, strengthening a classic result of Bentley and Saxe (Algorithmica, 1980).
ePrint: https://eprint.iacr.org/2019/377
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .