Non-Adaptive Data Structure Bounds For Dynamic Predecessor Search

Document Type

Paper

Publication Date

2017

Published In

Electronic Colloquium On Computational Complexity

Abstract

In this work, we continue the examination of the role non-adaptivity} plays in maintaining dynamic data structures, initiated by Brody and Larsen [BL15].. We consider nonadaptive data structures for predecessor search in the w-bit cell probe model. Predecessor search is one of the most well-studied data structure problems. For this problem, using non-adaptivity comes at a steep price. We provide exponential cell probe complexity separations between (i) adaptive and non-adaptive data structures and (ii) non-adaptive and memoryless data structures for predecessor search.

Keywords

dynamic data structures, encoding, Predecessor Search

Link to Full Text

Share

COinS