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.

A classic data structure of van Emde Boas [vEB75] solves dynamic predecessor search in O(\log \log m) probes; this data structure is adaptive. For dynamic data structures which make nonadaptive updates, we show the cell probe complexity is O\left(\min\{\frac{\log m}{\log(w/\log m)}, \frac{n\log m}{w}\}\right). We also give a nearly-matching \Omega\left(\min\{\frac{\log m}{\log w}, \frac{n \log m}{w \log w}\}\right) lower bound. We also give an \Omega(m) lower bound for memoryless data structures.
Our lower bound technique is tailored to nonadaptive (as opposed to memoryless) updates and should be of independent interest.