Nearly optimal separation between partially and fully retroactive data structures
DOI10.4230/LIPICS.SWAT.2018.33zbMATH Open1477.68077arXiv1804.06932MaRDI QIDQ5116497FDOQ5116497
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Which problems have strongly exponential complexity?
- On a class of \(O(n^ 2)\) problems in computational geometry
- Subquadratic algorithms for 3SUM
- Towards polynomial lower bounds for dynamic problems
- Making data structures persistent
- Optimal dynamic vertical ray shooting in rectilinear planar subdivisions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- Retroactive data structures
- Fully retroactive approximate range and nearest neighbor searching
- Polylogarithmic fully retroactive priority queues via hierarchical checkpointing
- Cloning Voronoi diagrams via retroactive data structures
- Higher lower bounds from the 3SUM conjecture
- More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems
- Conditional lower bounds for space/time tradeoffs
- On some fine-grained questions in algorithms and complexity
- Matching triangles and basing hardness on an extremely popular conjecture
Cited In (5)
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)
