2026-07-28T13:43:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6225 2024-03-06T10:37:45Z ddc:004 open_access

Deterministic Time-Space Trade-Offs for k-SUM Lincoln, Andrea Vassilevska Williams, Virginia Wang, Joshua R. Williams, R. Ryan 3SUM kSUM time-space tradeoff algorithm 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*lg(lg(n))/lg(n)) and space O(sqrt(n*lg(n)/lg(lg(n)))). In general, any polylogarithmic-time improvement over quadratic time for 3-SUM can be converted into an algorithm with an identical time improvement but low space complexity as well. - 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. - For k >= 4, k-SUM is in deterministic O(n^{k-2+2/k}) time and O(sqrt(n)) space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrea Lincoln and Virginia Vassilevska Williams and Joshua R. Wang and R. Ryan Williams 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.58 urn:nbn:de:0030-drops-62250 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.58 eng https://creativecommons.org/licenses/by/3.0/legalcode