Subquadratic algorithms for 3SUM
From MaRDI portal
Publication:2482729
Recommendations
Cites work
- Fusion trees can be implemented with AC^0 instructions only
- scientific article; zbMATH DE number 1351079 (Why is no real title available?)
- scientific article; zbMATH DE number 742994 (Why is no real title available?)
- Introduction to algorithms
- 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
- Surpassing the information theoretic bound with fusion trees
- Universal hashing and \(k\)-wise independent random variables via integer arithmetic without primes
Cited in
(43)- A (slightly) faster algorithm for Klee's measure problem
- Capturing points with a rotating polygon (and a 3D extension)
- Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model
- Four Soviets walk the dog: improved bounds for computing the Fréchet distance
- Subquadratic algorithms for algebraic 3SUM
- 3SUM, 3XOR, triangles
- Connectivity oracles for graphs subject to vertex failures
- Dynamic set intersection
- Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard
- Faster all-pairs shortest paths via circuit complexity
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Subquadratic algorithms for algebraic generalizations of 3SUM
- Deterministic time-space trade-offs for k-SUM
- More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems
- On the least trimmed squares estimator
- More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems
- Tighter connections between Formula-SAT and shaving logs
- A subquadratic algorithm for 3XOR
- On nondeterministic derandomization of Freivalds' algorithm: consequences, avenues and algorithmic progress
- From circuit complexity to faster all-pairs shortest paths
- On Multidimensional and Monotone k-SUM
- Nearly optimal separation between partially and fully retroactive data structures
- Improved subquadratic 3SUM
- Necklaces, convolutions, and \(X+Y\)
- Algorithms and Data Structures
- How fast can we play Tetris greedily with rectangular pieces?
- Universal Hashing via Integer Arithmetic Without Primes, Revisited
- Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
- Removing additive structure in 3SUM-based reductions
- Faster combinatorial \(k\)-clique algorithms
- \(k\)-SUM in the sparse regime: complexity and applications
- On Wagner's k-tree algorithm over integers
- 3SUM in preprocessed universes: faster and simpler
- Fine-grained complexity in a world without cryptography
- A k-swap local search for makespan scheduling
- Deterministic 3SUM-hardness
- Conditional lower bounds for dynamic geometric measure problems
- Improved algebraic degeneracy testing
- Conditional lower bounds for dynamic geometric measure problems
- Hopcroft's problem, log* shaving, two-dimensional fractional cascading, and decision trees
- Exploring the approximability landscape of 3SUM
- Faster combinatorial k-clique algorithms
- Into the square: on the complexity of some quadratic-time solvable problems
This page was built for publication: Subquadratic algorithms for 3SUM
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2482729)
