Nearly optimal separation between partially and fully retroactive data structures

DOI10.4230/LIPICS.SWAT.2018.33MaRDI QIDQ5116497zbMATH OpenFDO

Authors Lijie Chen, Erik D. Demaine, Yuzhou Gu, Yinzhan Xu, Yuancheng Yu, Virginia Vassilevska Williams

Publication date 25 August 2020

Full work available at URL https://arxiv.org/abs/1804.06932

zbMATH Keywords

retroactive data structureconditional lower bound

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Polylogarithmic fully retroactive priority queues via hierarchical checkpointing
• Retroactive data structures
• scientific article; zbMATH DE number 6469156
• Logarithmic Lower Bounds in the Cell-Probe Model
• Fully retroactive approximate range and nearest neighbor searching

Cites work

• scientific article; zbMATH DE number 437541 (Why is no real title available?)
• scientific article; zbMATH DE number 5764825 (Why is no real title available?)
• Cloning Voronoi diagrams via retroactive data structures
• Conditional lower bounds for space/time tradeoffs
• Fully retroactive approximate range and nearest neighbor searching
• Higher lower bounds from the 3SUM conjecture
• Making data structures persistent
• Matching triangles and basing hardness on an extremely popular conjecture
• More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems
• On a class of \(O(n^ 2)\) problems in computational geometry
• On some fine-grained questions in algorithms and complexity
• Optimal dynamic vertical ray shooting in rectilinear planar subdivisions
• Polylogarithmic fully retroactive priority queues via hierarchical checkpointing
• Retroactive data structures
• Subquadratic algorithms for 3SUM
• Towards polynomial lower bounds for dynamic problems
• Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
• Which problems have strongly exponential complexity?

Cited in

(8)

• Conditional lower bounds for dynamic geometric measure problems
• Upper and lower bounds for fully retroactive graph problems
• Conditional lower bounds for dynamic geometric measure problems
• How fast can we play Tetris greedily with rectangular pieces?
• Polylogarithmic fully retroactive priority queues via hierarchical checkpointing
• scientific article; zbMATH DE number 6469156 (Why is no real title available?)
• Anti-persistence
• Deterministic 3SUM-hardness

This page was built for publication: Nearly optimal separation between partially and fully retroactive data structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5116497)