Open Collections

Lower bounds on non-adaptive data structures for median and predecessor search

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Computer science; Information and communication, circuits; Theoretical computer science

video/mp4

Author affiliation: University of Washington

2017-09-17

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/63056

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/