On Multidimensional and Monotone k-SUM

DOI10.4230/LIPIcs.MFCS.2017.50zbMath1441.68092OpenAlexW2774970984MaRDI QIDQ5111265

Chris Umans, Chloe Ching-Yun Hsu

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 3SUM, 3XOR, triangles
• On a class of \(O(n^ 2)\) problems in computational geometry
• Subquadratic algorithms for 3SUM
• Towards polynomial lower bounds for dynamic problems
• Losing Weight by Gaining Edges
• Clustered Integer 3SUM via Additive Combinatorics
• Threesomes, Degenerates, and Love Triangles
• Higher Lower Bounds from the 3SUM Conjecture
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy
• On Hardness of Jumbled Indexing
• Finding, minimizing, and counting weighted subgraphs
• Exact Weight Subgraphs and the k-Sum Conjecture
• Lower bounds for linear degeneracy testing

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