Non-Adaptive Data Structure Bounds For Dynamic Predecessor Search
Electronic Colloquium On Computational Complexity
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.
dynamic data structures, encoding, Predecessor Search
Joseph W. Boninger , '16; Joshua Brody; and Owen Kephart , '18.
"Non-Adaptive Data Structure Bounds For Dynamic Predecessor Search".
Electronic Colloquium On Computational Complexity.