Paper by Erik D. Demaine

Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, Yinzhan Xu, and Yuancheng Yu, “Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures”, in Proceedings of the 20th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), Malmö, Sweden, June 18–20, 2018.

Since the introduction of retroactive data structures at SODA 2004, a major unsolved problem has been to bound the gap between the best partially retroactive data structure (where changes can be made to the past, but only the present can be queried) and the best fully retroactive data structure (where the past can also be queried) for any problem. It was proved in 2004 that any partially retroactive data structure with operation time Top(nm) can be transformed into a fully retroactive data structure with operation time O(√m · Top(nm)), where n is the size of the data structure and m is the number of operations in the timeline [7]. But it has been open for 14 years whether such a gap is necessary.

In this paper, we prove nearly matching upper and lower bounds on this gap for all n and m. We improve the upper bound for n ≪ √m by showing a new transformation with multiplicative overhead n log m. We then prove a lower bound of min{n log m, √m}1 − o(1) assuming any of the following conjectures:

Our lower bound construction illustrates an interesting power of fully retroactive queries: they can be used to quickly solve batched pair evaluation. We believe this technique can prove useful for other data structure lower bounds, especially dynamic ones.

The paper is available in PDF (340k).
See information on file formats.
[Google Scholar search]

Related papers:
FullyRetroactive_WADS2015 (Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing)
Retroactive_TALG (Retroactive Data Structures)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated May 7, 2018 by Erik Demaine.