Deterministic Time-Space Tradeoffs for k-SUM

Wednesday, June 8, 2016 - 4:00pm to 5:00pm
Andrea Lincoln

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 studied in the word-RAM model; when the numbers are reals, the complexity is studied in the real-RAM model, and space is measured by the number of reals held in memory at any point.

We present a time and space efficient deterministic self-reduction for the k-SUM problem which holds for both models, and has many interesting consequences. To illustrate:
* 3-SUM is in deterministic time O(n^2 lglg(n)/lg(n)) and space O(\sqrt{n lg(n)/lglg(n)}), extending the results of Gold and Sharir.
* 3-SUM is in deterministic time O(n^2) and space O(\sqrt n), derandomizing an algorithm of Wang.
* A popular conjecture states that 3-SUM requires n^{2-o(1)} time on the word-RAM. We show that the 3-SUM Conjecture is in fact equivalent to the (seemingly weaker) conjecture that every O(n^{.51})-space algorithm for 3-SUM requires at least n^{2-o(1)} time on the word-RAM.

Joint work with Virginia Vassilevska Williams, Josh Wang and Ryan Williams.