← 研踪 PaperTrailarXiv:2510.08185 · v3
k-SUM Hardness Implies Treewidth-SETH
首次提交 2025-10-09 21:13
版本更新 2026-10-26 01:21
雷达观测 2026-10-29 00:36
摘要
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>0$ 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 $δ>0$ 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.
作者备注：SODA 2026
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v3 · 2026-10-26 01:21 · 最新观测版本
k-SUM Hardness Implies Treewidth-SETH
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>0$ 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 $δ>0$ 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.
查看此版本解读 →查看此版本原文 ↗