Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.)

share|improve this question
    
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. –  Ryan Williams Dec 5 '12 at 10:19
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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