Sivaramakrishnan Ramamoorthy (University of Washington)
Monday, March 6, 2017, 2:00pm
Title: Lower bounds on non-adaptive data structures for median and predecessor search
Abstract: 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. The main technical contribution of our work is a method to apply the famous Sunflower lemma to these problems.
Joint work with Anup Rao (UW)