Deterministic Time-Space Tradeoffs for k-SUM

Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang +1

Given a set of numbers, the $k$-SUM problem asks for a subset of $k$ numbers that sums to zero. When the numbers are integers, the time and space complexity of $k$-SUM is generally…