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 \gt 0\) and an algorithm which solves SAT in time \((2 - \varepsilon)^{\mathrm{tw}} |\phi|^{O(1)}\), where \(\mathrm{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 - \delta)\frac{k}{2}}\) for some \(\delta \gt 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\).