BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Lower bounds on non-adaptive data structures for median and predecessor search Natarajan Ramamoorthy, Sivaramakrishnan


We initiate the study of lower bounds for the median problem in the cell probe model. The algorithmic task is to maintain a subset of {1,2,....,m}, support insertion of elements and find the median of the set. Let $t_u,t_q,w$ denote the update time, the query time and the cell size of a data structure. We show that any data structure for the median problem must have $t_q \geq \Omega(m^(1/2(t_u+2))/(wt_u))$, when the updates are non-adaptive. An update is termed non-adaptive when locations of the cells accessed by the update algorithm is completely determined by the update value. For the predecessor search problem, we show that either $t_q \geq \Omega(\log m/(\log \log m + \log w))$ or $t_u \geq \Omega(m^(1/4(t_q+1)))$, when the queries are non-adaptive. This is joint work with Anup Rao.

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International