k-SUM Hardness Implies Treewidth-SETH

Michael Lampis

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 th…