Conditional lower bounds for dynamic geometric measure problems
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 1947378 (Why is no real title available?)
- A (slightly) faster algorithm for Klee's measure problem
- Answering UCQs under updates and in the presence of integrity constraints
- Better Data Structures for Colored Orthogonal Range Reporting
- Bringing order to special cases of Klee's measure problem
- Color-distance oracles and snippets
- Conditional hardness for sensitivity problems
- Dynamic Colored Orthogonal Range Searching.
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- Dynamic geometric data structures via shallow cuttings
- Dynamic geometric set cover, revisited
- Dynamic matrix inverse: improved algorithms and matching conditional lower bounds
- Dynamic parameterized problems and algorithms
- Efficient range searching for categorical and plain data
- Fast and Simple Connectivity in Graph Timelines
- Faster Online Matrix-Vector Multiplication
- Faster all-pairs shortest paths via circuit complexity
- Fine-Grained Complexity Theory (Tutorial)
- Fine-grained complexity theory: conditional lower bounds for computational geometry
- Further Results on Generalized Intersection Searching Problems: Counting, Reporting, and Dynamization
- GENERALIZED INTERSECTION SEARCHING PROBLEMS
- Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV
- Hardness of approximate nearest neighbor search
- Higher lower bounds from the 3SUM conjecture
- Hopcroft's problem, log-star shaving, 2D fractional cascading, and decision trees
- Introduction to algorithms.
- Lower bounds for dynamic algebraic problems
- Maintenance of configurations in the plane
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Mind the gap!
- Monochromatic triangles, triangle listing and APSP
- More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems
- Multidimensional binary search trees used for associative searching
- Near-optimal range reporting structures for categorical data
- Nearly optimal separation between partially and fully retroactive data structures
- New Upper Bounds in Klee’s Measure Problem
- On a class of \(O(n^ 2)\) problems in computational geometry
- On hardness of jumbled indexing
- On some fine-grained questions in algorithms and complexity
- On the complexity of the (approximate) nearest colored node problem
- On the convex layers of a planar set
- On the hardness of partially dynamic graph problems and connections to diameter
- Optimal and near-optimal algorithms for generalized intersection reporting on pointer machines
- Optimal packing and covering in the plane are NP-complete
- Popular conjectures as a barrier for dynamic planar graph algorithms
- Popular conjectures imply strong lower bounds for dynamic problems
- Semi-Online Maintenance of Geometric Optima and Measures
- Subquadratic algorithms for 3SUM
- The union of probabilistic boxes: Maintaining the volume
- Threesomes, degenerates, and love triangles
- Tight dynamic problem lower bounds from generalized BMM and OMv
- Towards polynomial lower bounds for dynamic problems
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- Worst-Case Efficient Dynamic Geometric Independent Set
This page was built for publication: Conditional lower bounds for dynamic geometric measure problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6955678)
