Deterministic 3SUM-hardness
From MaRDI portal
Cites work
- All non-trivial variants of 3-LDT are equivalent
- Clustered Integer 3SUM via Additive Combinatorics
- COMPUTING THE SET OF ALL THE DISTANT HORIZONS OF A TERRAIN
- Consequences of Faster Alignment of Sequences
- Deterministic time-space trade-offs for k-SUM
- Equivalences between triangle and range query problems
- Exact weight subgraphs and the k-sum conjecture
- Fast and Simple Connectivity in Graph Timelines
- Filling polyhedral molds.
- Finding a guard that sees most and a shop that sells most
- Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
- Finding, minimizing, and counting weighted subgraphs
- Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond
- Higher lower bounds from the 3SUM conjecture
- How hard is it to find (honest) witnesses?
- scientific article; zbMATH DE number 1875422 (Why is no real title available?)
- scientific article; zbMATH DE number 7650401 (Why is no real title available?)
- scientific article; zbMATH DE number 7740932 (Why is no real title available?)
- Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy
- Improved subquadratic 3SUM
- Joins via geometric resolutions. Worst case and beyond
- Losing weight by gaining edges
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Mind the gap!
- More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems
- Near-optimal linear decision trees for \(k\)-SUM and related problems
- Nearly optimal separation between partially and fully retroactive data structures
- New Lower Bounds for Convex Hull Problems in Odd Dimensions
- On a class of \(O(n^ 2)\) problems in computational geometry
- On Approximating the Depth and Related Problems
- On hardness of jumbled indexing
- On minimum-area hulls
- On the hardness of partially dynamic graph problems and connections to diameter
- On the least median square problem
- Pattern matching under polynomial transformation
- Perfect binary space partitions
- POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
- Preprocessing chains for fast dihedral rotations is hard or even impossible.
- Reducing \textsf{3SUM} to \textsf{Convolution-3SUM}
- Removing additive structure in 3SUM-based reductions
- Smallest k-enclosing rectangle revisited
- Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
- Subcubic equivalences between path, matrix, and triangle problems
- Subquadratic algorithms for 3SUM
- The dynamic k-mismatch problem
- Threesomes, degenerates, and love triangles
- Towards polynomial lower bounds for dynamic problems
Cited in
(3)
This page was built for publication: Deterministic 3SUM-hardness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6906383)
