Lower bounds for 3SUM with a free cache 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 &lt; 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.)
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.