Unconditional Boolean Dynamic Lower Bounds from Disjointness

Young Kun Ko

We prove an unconditional $\Omega ((\log n/\log \log n{)}^2)$ lower bound on the maximum of the worst-case update time and expected query time for the insert-only version of Patrascu's mult…