Fine-grained complexity theory: conditional lower bounds for computational geometry

DOI10.1007/978-3-030-80049-9_6MaRDI QIDQ2117766OpenAlexFDO

Authors Karl Bringmann

Publication date 22 March 2022

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

zbMATH Keywords

computational geometryfine-grained complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• On some fine-grained questions in algorithms and complexity
• Fine-Grained Complexity Theory (Tutorial)
• Towards hardness of approximation for polynomial time problems
• Parameterized computational geometry via decomposition theorems
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)

Cites work

• A new algorithm for optimal 2-constraint satisfaction and its implications
• An improved approximation algorithm for the discrete Fréchet distance
• Approximability of the discrete Fréchet distance
• Approximating the Fréchet distance for realistic curves in near linear time
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• Fine-Grained Complexity Theory (Tutorial)
• Fréchet distance under translation: conditional hardness and an algorithm via offline dynamic grid reachability
• Hardness of approximate nearest neighbor search
• Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds
• More applications of the polynomial method to algorithm design
• Multivariate fine-grained complexity of longest common subsequence
• Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
• On a class of \(O(n^ 2)\) problems in computational geometry
• On some fine-grained questions in algorithms and complexity
• On the complexity of \(k\)-SAT
• On the difference between closest, furthest, and orthogonal pairs: nearly-linear vs barely-subquadratic complexity
• On the hardness of approximate and exact (bichromatic) maximum inner product
• Polyline simplification has cubic complexity
• SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension
• Tight hardness results for maximum weight rectangles
• Tighter connections between Formula-SAT and shaving logs
• Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees

Cited in

(3)

• Bounds on the complexity of halfspace intersections when the bounded faces have small dimension
• scientific article; zbMATH DE number 3883608 (Why is no real title available?)
• Density-based clustering in MapReduce with guarantees on parallel time, space, and solution quality

This page was built for publication: Fine-grained complexity theory: conditional lower bounds for computational geometry

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