Paper by Erik D. Demaine

Reference:

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.

BibTeX

@InProceedings{RetroactiveSeparation_ISAAC2022,
  AUTHOR        = {Lily Chung and Erik D. Demaine and Della Hendrickson and Jayson Lynch},
  authororig    = {Lily Chung and Erik D. Demaine and Dylan Hendrickson and Jayson Lynch},
  TITLE         = {Lower Bounds on Retroactive Data Structures},
  BOOKTITLE     = {Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  bookurl       = {https://isa.hanyang.ac.kr/isaac2022/},
  SERIES        = {LIPIcs},
  ADDRESS       = {Seoul, Korea},
  MONTH         = {December 19--21},
  YEAR          = 2022,
  PAGES         = {32:1--32:13},

  withstudent   = 1,
  doi           = {https://dx.doi.org/10.4230/LIPIcs.ISAAC.2022.32},
  dblp          = {https://dblp.org/rec/conf/isaac/ChungDHL22},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.4230/LIPIcs.ISAAC.2022.32">LIPIcs</A>.
                   <P>
                   The full paper is available as <A HREF="https://arXiv.org/abs/2211.14664">arXiv:2211.14664</A>.},
  papers        = {RetroactiveSeparation_SWAT2018; FullyRetroactive_WADS2015; Retroactive_TALG},
}

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) · m^1 − 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 m^o(1) factor common in fine-grained complexity.

Comments:

This paper is also available from LIPIcs.

The full paper is available as arXiv:2211.14664.

Availability:

The paper is available in PDF (723k).

See information on file formats.

[Google Scholar search]

Related papers:

RetroactiveSeparation_SWAT2018 (Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures)

FullyRetroactive_WADS2015 (Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing)

Retroactive_TALG (Retroactive Data Structures)