{"ID":2858153,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.08185","arxiv_id":"2510.08185","title":"k-SUM Hardness Implies Treewidth-SETH","abstract":"We show that if k-SUM is hard, in the sense that the standard algorithm is essentially optimal, then a variant of the SETH called the Primal Treewidth SETH is true. Formally: if there is an $\\varepsilon\u003e0$ and an algorithm which solves SAT in time $(2-\\varepsilon)^{tw}|φ|^{O(1)}$, where $tw$ is the width of a given tree decomposition of the primal graph of the input, then there exists a randomized algorithm which solves k-SUM in time $n^{(1-δ)\\frac{k}{2}}$ for some $δ\u003e0$ and all sufficiently large $k$. We also establish an analogous result for the k-XOR problem, where integer addition is replaced by component-wise addition modulo $2$. As an application of our reduction we are able to revisit tight lower bounds on the complexity of several fundamental problems parameterized by treewidth (Independent Set, Max Cut, $k$-Coloring). Our results imply that these bounds, which were initially shown under the SETH, also hold if one assumes the k-SUM or k-XOR Hypotheses, arguably increasing our confidence in their validity.","short_abstract":"We show that if k-SUM is hard, in the sense that the standard algorithm is essentially optimal, then a variant of the SETH called the Primal Treewidth SETH is true. Formally: if there is an $\\varepsilon\u003e0$ and an algorithm which solves SAT in time $(2-\\varepsilon)^{tw}|φ|^{O(1)}$, where $tw$ is the width of a given tre...","url_abs":"https://arxiv.org/abs/2510.08185","url_pdf":"https://arxiv.org/pdf/2510.08185v2","authors":"[\"Michael Lampis\"]","published":"2025-10-09T13:13:21Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DS\"]","methods":"[]","has_code":false}