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+\Omega (1)}$ points. A…