On Multidimensional and Monotone k-SUM

DOI10.4230/LIPICS.MFCS.2017.50MaRDI QIDQ5111265zbMATH OpenOpenAlexFDO

Authors Chloe Ching-Yun Hsu, Chris Umans

Publication date 26 May 2020

Full work available at URL https://doi.org/10.4230/LIPIcs.MFCS.2017.50

zbMATH Keywords

3-SUMk-SUMmonotone 3-SUMstrong 3-SUM conjecture

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Exact enumeration problems, generating functions (05A15)

Recommendations

• Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy
• Deterministic time-space trade-offs for \(k\)-SUM
• Improved subquadratic 3SUM
• Space-efficient randomized algorithms for \(k\)-sum
• Threesomes, degenerates, and love triangles

Cites work

• scientific article; zbMATH DE number 1351079 (Why is no real title available?)
• 3SUM, 3XOR, triangles
• Clustered Integer 3SUM via Additive Combinatorics
• Exact weight subgraphs and the \(k\)-sum conjecture
• Finding, minimizing, and counting weighted subgraphs
• Higher lower bounds from the 3SUM conjecture
• How hard is it to find (honest) witnesses?
• Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy
• Losing weight by gaining edges
• Lower bounds for linear degeneracy testing
• On a class of \(O(n^ 2)\) problems in computational geometry
• On hardness of jumbled indexing
• On the possibility of faster \textsc{SAT} algorithms
• Subquadratic algorithms for 3SUM
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• Threesomes, degenerates, and love triangles
• Towards polynomial lower bounds for dynamic problems

Cited in

(5)

• Deterministic time-space trade-offs for \(k\)-SUM
• Exact Parameterized Multilinear Monomial Counting via k-Layer Subset Convolution and k-Disjoint Sum
• Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
• Removing additive structure in 3SUM-based reductions
• Multidimensional Hadamard composition and sums with linear constraints upon summation indices

This page was built for publication: On Multidimensional and Monotone k-SUM

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111265)