Threesomes, Degenerates, and Love Triangles
From MaRDI portal
Publication:4561510
DOI10.1145/3185378zbMath1422.68112arXiv1404.0799OpenAlexW2963410133MaRDI QIDQ4561510
Publication date: 6 December 2018
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1404.0799
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Randomized algorithms (68W20)
Related Items (28)
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Dynamic Set Intersection ⋮ Geometric pattern matching reduces to \(k\)-SUM ⋮ Four Soviets walk the dog: improved bounds for computing the Fréchet distance ⋮ Mind the gap! ⋮ Subquadratic algorithms for algebraic 3SUM ⋮ A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model ⋮ Time and space efficient collinearity indexing ⋮ Searching for Point Locations Using Lines ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Online recognition of dictionary with one gap ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ A subquadratic algorithm for 3XOR ⋮ Geometric Pattern Matching Reduces to k-SUM. ⋮ Improved subquadratic 3SUM ⋮ Capturing points with a rotating polygon (and a 3D extension) ⋮ Into the square: on the complexity of some quadratic-time solvable problems ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ On Multidimensional and Monotone k-SUM ⋮ Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy ⋮ Dynamic data structures for timed automata acceptance ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model ⋮ Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems ⋮ On 3SUM-hard problems in the decision tree model ⋮ 3SUM, 3XOR, triangles ⋮ A comparative study of dictionary matching with gaps: limitations, techniques and challenges
This page was built for publication: Threesomes, Degenerates, and Love Triangles
