On Dynamic Bit-Probe Complexity

Abstract

This paper presents several advances in the understanding of dynamic data structures in the bit-probe model:

• We improve the lower bound record for dynamic language membership problems to $\Omega((\frac{{\rm lg}\ n}{\rm lg \ lg \ {\it n}})^{2})$. Surpassing $\Omega({\rm lg} \ {\it n})$ was listed as the first open problem in a survey by Miltersen.

• We prove a bound of $\Omega(\frac{{\rm lg}\ n}{\rm lg \ lg \ lg \ {\it n}})$ for maintaining partial sums in ${\mathbb Z}/2{\mathbb Z}$. Previously, the known bounds were $\Omega(\frac{{\rm lg}\ n}{\rm lg \ lg \ {\it n}})$ and $O({\rm lg}\ n)$.

• We prove a surprising and tight upper bound of $O(\frac{{\rm lg} \ {\it n}}{\rm lg \ lg \ {\it n}})$ for predecessor problems. We use this to obtain the same upper bound for dynamic word and prefix problems in group-free monoids.