Subquadratic algorithms for 3SUM

DOI10.1007/S00453-007-9036-3zbMath1147.68861DBLPjournals/algorithmica/BaranDP08OpenAlexW2049647076WikidataQ56288895 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

zbMATH Keywords

3SUMRandomizationWord RAM

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (23)

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) ⋮ Removing additive structure in 3SUM-based reductions ⋮ 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