6
$\begingroup$

Consider the 3SUM problem: given a set $S$ of $n$ numbers identify $x$,$y$,$z$, s.t $x + y = z$. It is believed that the simple $O(n^2)$ algorithm is the best possible; reductions from 3SUM have been used to prove lower bounds for other problems assuming 3SUM is hard [Patrascu 2010].

Is it possible to prove that a small amount $n^\delta$ ($\delta < 1$) of free cache does not help for 3SUM? (An algorithm can store information in the cache and access it for free while accesses to regular RAM cost 1.)

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ I don't understand the question. Is the cache supposed to be read-only information chosen prior to the input (i.e., "non-uniform advice")? Or can one both read and write to these $n^{\delta}$ bits, at literally no cost? Using "almost-linear" hashing, you can reduce 3SUM on $n$ numbers to $O(t^2)$ instances of 3SUM on $O(n/t)$ numbers. So if you can really access this $n^{\delta}$ space for free, then by setting $t$ so that $(n/t)\log n \approx n^{\delta}$ you get a $n^{2-\varepsilon}$ 3SUM algorithm, as the $O(t^2)$ instances would take about $O(n/t)$ time each. $\endgroup$
    – Ryan Williams
    Dec 5, 2012 at 10:19

1 Answer 1

Reset to default
7
$\begingroup$

Well, sure, it's possible. But since we basically don't know how to prove that anything is hard, it doesn't look easy.

In the mid 90s I proved an $\Omega(n^2)$ lower bound for 3SUM in a variant of the linear decision tree model; my proof was later simplified by Ailon and Chazelle. This model of computation has nothing corresponding to "memory"; the running time of an algorithm is defined simply as the worst-case number of (generalized) comparisons. So adding a cache won't break these lower bounds; to beat $O(n^2)$ time, you have to do some non-obvious computation with the data in the cache.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.