Further Unifying the Landscape of Cell Probe Lower Bounds

Kasper Green Larsen, Jonathan Lindegaard Starup, Jesper Steensgaard

In a landmark paper, Pǎtraşcu demonstrated how a single lower bound for the static data structure problem of reachability in the butterfly graph, could be used to derive a wealth o…