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

<p>In the mid 90s I proved <a href="http://compgeom.cs.uiuc.edu/~jeffe/pubs/linsat.html">an $\Omega(n^2)$ lower bound for 3SUM</a> in a variant of the linear decision tree model; my proof was later simplified by <a href="http://www.cs.princeton.edu/~chazelle/pubs/lindegen-jacm.pdf">Ailon and Chazelle</a>.  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 <em>computation</em> with the data in the cache. </p>

CC BY-SA 3.0
2012-12-03T17:13:53.840Z
2012-12-03T17:13:53.840Z
Jeffε
<p>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].</p>

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

CC BY-SA 3.0
2012-12-05T10:19:13.190Z
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
<lower-bounds>
Lower bounds for 3SUM with a free cache
Arvind Arasu
# Lower bounds for 3SUM with a free cache

(Asked by: username_0 on 2012-12-03)

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

**Tags:** lower-bounds

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2012-12-03. Score: 7

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](http://compgeom.cs.uiuc.edu/~jeffe/pubs/linsat.html) in a variant of the linear decision tree model; my proof was later simplified by [Ailon and Chazelle](http://www.cs.princeton.edu/~chazelle/pubs/lindegen-jacm.pdf). 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.


---

