Exploring the approximability landscape of 3SUM
From MaRDI portal
Cites work
- A subquadratic approximation scheme for partition
- All non-trivial variants of 3-LDT are equivalent
- An efficient fully polynomial approximation scheme for the Subset-Sum problem.
- Approximation algorithms and hardness for n-pairs shortest paths and all-nodes shortest cycles
- Bellman-Ford is optimal for shortest Hop-bounded paths
- Better approximations for tree sparsity in nearly-linear time
- Consequences of Faster Alignment of Sequences
- Distributed PCP theorems for hardness of approximation in P
- Exact weight subgraphs and the k-sum conjecture
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Finding longest approximate periodic patterns
- Finding, minimizing, and counting weighted subgraphs
- Fine-grained complexity of analyzing compressed data: quantifying improvements over decompress-and-solve
- Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV
- Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond
- scientific article; zbMATH DE number 3644795 (Why is no real title available?)
- scientific article; zbMATH DE number 7204473 (Why is no real title available?)
- scientific article; zbMATH DE number 7646025 (Why is no real title available?)
- scientific article; zbMATH DE number 7788446 (Why is no real title available?)
- Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy
- Improved subquadratic 3SUM
- More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems
- Necklaces, convolutions, and \(X+Y\)
- On a class of \(O(n^ 2)\) problems in computational geometry
- On hardness of jumbled indexing
- On Multidimensional and Monotone k-SUM
- On problems equivalent to \((\min,+)\)-convolution
- On some fine-grained questions in algorithms and complexity
- Polygon placement revisited: (degree of freedom + 1)-SUM hardness and an improvement via offline dynamic rectangle union
- Reducing \textsf{3SUM} to \textsf{Convolution-3SUM}
- Removing additive structure in 3SUM-based reductions
- SETH-based Lower Bounds for Subset Sum and Bicriteria Path
- Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
- Subquadratic algorithms for 3SUM
- Threesomes, degenerates, and love triangles
- Towards hardness of approximation for polynomial time problems
- Towards polynomial lower bounds for dynamic problems
- Towards tight approximation bounds for graph diameter and eccentricities
- Translating Hausdorff is hard: fine-grained lower bounds for Hausdorff distance under translation
This page was built for publication: Exploring the approximability landscape of 3SUM
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7253090)
