Lily Chung, Erik D. Demaine, Della Hendrickson, and Jayson Lynch, “Lower Bounds on Retroactive Data Structures”, in Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022), LIPIcs, Seoul, Korea, December 19–21, 2022, 32:1–32:13.
Abstract:
We prove essentially optimal fine-grained lower bounds on the gap between a
data structure and a partially retroactive version of the same data structure.
Precisely, assuming any one of three standard conjectures, we describe a
problem that has a data structure where operations run in
O(T(n, m)) time per operation, but any
partially retroactive version of that data structure requires
T(n, m) ·
m1 − o(1) worst-case time per
operation, where n is the size of the data structure at any time and
m is the number of operations. Any data structure with operations
running in O(T(n, m)) time per operation can
be converted (via the “rollback method”) into a partially
retroactive data structure running in
O(T(n, m) \cdot m) time per operation,
so our lower bound is tight up to an mo(1) factor
common in fine-grained complexity.