Department of
Applied
Mathematics

Lower bounds on Non-adaptive Data Structures for Median and Predecessor search

Anup Rao

Abstract

(joint work with Siva Ramamoorthy)

What is the best way to maintain a subset of {1,2,...,m} so that the median of the set can be easily recovered? We are interested in the algorithms that access the fewest memory locations when adding an element to the set and computing the median of the set. We prove the first lower bounds for such algorithms. We say that the algorithm handles insertions non-adaptively if the locations of memory accessed depend only on the element being inserted, and not on the contents of the memory. If the algorithm handles insertions non-adaptively, then our lower bounds imply that Binary Search Trees are essentially optimal (our results give a more general tradeoff between the parameters of the algorithm). In addition, we investigate the predecessor search problem, where the algorithm is required to compute the predecessor of any element in the set. Here we prove that if computing the predecessors can be done non-adaptively, then again Binary Search Trees are essentially optimal. Our results follow from a novel application of the Sunflower Lemma to these questions.