Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Predecessor Search:
TR17-050 | 15th March 2017
Joe Boninger, Joshua Brody, Owen Kephart

Non-Adaptive Data Structure Bounds for Dynamic Predecessor Search

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 ... more >>>

TR20-003 | 15th January 2020
Giuseppe Persiano, Kevin Yeo

Tight Static Lower Bounds for Non-Adaptive Data Structures

In this paper, we study the static cell probe complexity of non-adaptive data structures that maintain a subset of $n$ points from a universe consisting of $m=n^{1+\Omega(1)}$ points. A data structure is defined to be non-adaptive when the memory locations that are chosen to be accessed during a query depend ... more >>>

ISSN 1433-8092 | Imprint