Lower bounds for linear degeneracy testing

DOI10.1145/1059513.1059515zbMath1286.68172OpenAlexW1986338919MaRDI QIDQ5900514

Bernard Chazelle, Nir Ailon

Publication date: 21 December 2008

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.86.1190

zbMATH Keywords

lower boundcomputational geometrylinear decision trees

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (13)

Exact Weight Subgraphs and the k-Sum Conjecture ⋮ Geometric pattern matching reduces to \(k\)-SUM ⋮ Four Soviets walk the dog: improved bounds for computing the Fréchet distance ⋮ Subquadratic algorithms for algebraic 3SUM ⋮ A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model ⋮ Practical Attacks on Relational Databases Protected via Searchable Encryption ⋮ Geometric Pattern Matching Reduces to k-SUM. ⋮ Improved subquadratic 3SUM ⋮ On Multidimensional and Monotone k-SUM ⋮ Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy ⋮ Fast dimension reduction using Rademacher series on dual BCH codes ⋮ On 3SUM-hard problems in the decision tree model ⋮ 3SUM, 3XOR, triangles

This page was built for publication: Lower bounds for linear degeneracy testing