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 ε > 0 and an algorithm which solves SAT in time (2 -ε) 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-δ) 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.

An interesting aspect of our proof is that we rely on two key ideas from different topics. First, inspired by the classical perfect hashing scheme of Fredman, Komlós, and Szemerédi, we show that k-SUM admits an interactive proof protocol using integers of absolute value only O(n k/2 ). Second, using the intuition that SAT formulas of treewidth tw can encode the workings of alternating Turing machines using tw bits of space, we are able to encode this protocol into a formula of treewidth roughly k 2 log n and obtain the main result. 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.