Kevin Yeo

activity

20172026

collaborators

Showing cs.DSShow all

2 papers · 1 filter

cs.DS2020

Tight Static Lower Bounds for Non-Adaptive Data Structures

Giuseppe Persiano, Kevin Yeo

In this paper, we study the static cell probe complexity of non-adaptive data structures that maintain a subset of $n$ points from a universe consisting of $m = n^{1 + Ω (1)}$ points. A…

cs.DS2019

Lower Bounds for Oblivious Near-Neighbor Search

Kasper Green Larsen, Tal Malkin, Omri Weinstein +1

We prove an $Ω (d l g n / (l g l g n)^{2})$ lower bound on the dynamic cell-probe complexity of statistically $oblivious$ approximate-near-neighbor search ( $ANN$ ) over…