Subquadratic algorithms for 3SUM
From MaRDI portal
Publication:2482729
DOI10.1007/s00453-007-9036-3zbMath1147.68861OpenAlexW2049647076WikidataQ56288895 ScholiaQ56288895MaRDI QIDQ2482729
Erik D. Demaine, Mihai Pǎtraşcu, Ilya Baran
Publication date: 23 April 2008
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-007-9036-3
Related Items (22)
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Dynamic Set Intersection ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Four Soviets walk the dog: improved bounds for computing the Fréchet distance ⋮ Subquadratic algorithms for algebraic 3SUM ⋮ How fast can we play Tetris greedily with rectangular pieces? ⋮ Universal Hashing via Integer Arithmetic Without Primes, Revisited ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the least trimmed squares estimator ⋮ A subquadratic algorithm for 3XOR ⋮ Improved subquadratic 3SUM ⋮ Necklaces, convolutions, and \(X+Y\) ⋮ Capturing points with a rotating polygon (and a 3D extension) ⋮ Into the square: on the complexity of some quadratic-time solvable problems ⋮ Unnamed Item ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard ⋮ A (slightly) faster algorithm for Klee's measure problem ⋮ On Multidimensional and Monotone k-SUM ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ 3SUM, 3XOR, triangles
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fusion trees can be implemented with \(AC^0\) instructions only
- Surpassing the information theoretic bound with fusion trees
- On a class of \(O(n^ 2)\) problems in computational geometry
- Randomized Sorting in O(nloglogn) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations
- Universal hashing and k-wise independent random variables via integer arithmetic without primes
This page was built for publication: Subquadratic algorithms for 3SUM
