Reducing \textsf{3SUM} to \textsf{Convolution-3SUM}

DOI10.1137/1.9781611976014.1MaRDI QIDQ6538723zbMATH OpenFDO

Authors Timothy M. Chan, Qizheng He

Publication date 14 May 2024

Full work available at URL https://doi.org/10.1137/1.9781611976014.1

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited in

(10)

• Deterministic 3SUM-hardness
• Fast convolutions for near-convex sequences
• Improved algebraic degeneracy testing
• Computing generalized convolutions faster than brute force
• Unbalanced triangle detection and enumeration hardness for unions of conjunctive queries
• 3sum and related problems in fine-grained complexity (invited talk)
• Translating Hausdorff is hard: fine-grained lower bounds for Hausdorff distance under translation
• Worst-case to expander-case reductions: derandomized and generalized
• Exploring the approximability landscape of 3SUM
• (Multivariate) k-SUM as barrier to succinct computation

This page was built for publication: Reducing \textsf{3SUM} to \textsf{Convolution-3SUM}

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