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.