Nearly optimal separation between partially and fully retroactive data structures
From MaRDI portal
Publication:5116497
DOI10.4230/LIPICS.SWAT.2018.33zbMATH Open1477.68077arXiv1804.06932MaRDI QIDQ5116497FDOQ5116497
Yinzhan Xu, Yuzhou Gu, Lijie Chen, Erik D. Demaine, Virginia Vassilevska Williams, Yuancheng Yu
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
- Title not available (Why is that?)
- 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 (4)
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)
