<p>The following excellent video:</p>
<p><a href="https://www.youtube.com/watch?v=YRiyqc99kd0&amp;t=2661s" rel="nofollow noreferrer">https://www.youtube.com/watch?v=YRiyqc99kd0&amp;t=2661s</a></p>
<p>and this one:</p>
<p><a href="https://www.youtube.com/watch?v=x-HskkxUuVI&amp;t=1965s" rel="nofollow noreferrer">https://www.youtube.com/watch?v=x-HskkxUuVI&amp;t=1965s</a></p>
<p>Deals with this issue and Fine Grained Approach to Complexity in general.</p>

CC BY-SA 4.0
2020-07-11T15:44:25.307Z
2020-07-11T15:44:25.307Z
Avi Tal
<p>I think currently it is not even known if strong ETH and 3SUM are related, see e.g. [1]. For the relation of ETH and 3SUM, note that ETH really cannot be refuted by improving polynomial time algorithms (at least via Karp reductions) because it would only improve constants in the exponent of the runtime. In particular, if we reduce 3-SAT to a 3SUM instance of size <span class="math-container">$2^{O(n)}$</span>, it will not refute ETH, and if we reduce 3-SAT to a 3SUM instance of size <span class="math-container">$2^{o(n)}$</span>, it will refute ETH regardless of the complexity of 3SUM.</p>
<p>[1] Virginia V. Williams. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). IPEC 2015. <a href="https://drops.dagstuhl.de/opus/volltexte/2015/5568/pdf/5.pdf" rel="noreferrer">https://drops.dagstuhl.de/opus/volltexte/2015/5568/pdf/5.pdf</a></p>

CC BY-SA 4.0
2020-07-11T06:44:47.873Z
2020-07-11T06:44:47.873Z
Laakeri
<p>In the recent question <a href="https://cstheory.stackexchange.com/questions/47186/3sum-complexity-a-special-case">3SUM Complexity—A special(?) Case</a> I asked about why the set size <span class="math-container">$O(n^3)$</span> was an interesting value for the 3SUM Problem and got a nice answer. My reference was the paper “Consequences of Faster Alignment of Sequences” by
Abboud, Vassilevska Williams, and Weimann available [here][1]. The term <em>of a certain size</em> in the title of this question refers to the support set being <span class="math-container">$\{-n^3,\ldots,n^3\}$</span>:</p>
<p><strong>Conjecture 1 (3-SUM Conjecture)</strong> <em>In the Word RAM model with words of <span class="math-container">$O(\log n)$</span> bits, any algorithm requires <span class="math-container">$n^{2−o(1)}$</span> time in expectation to determine whether three sets
<span class="math-container">$A,B,C \subset \{−n^3,\ldots,n^3\}$</span> with <span class="math-container">$|A| = |B| = |C| = n$</span>
integers contain three elements <span class="math-container">$a∈A,b∈B,c∈C$</span> with <span class="math-container">$a+b+c=0.$</span></em></p>
<p>If there was an algorithm solving <em>this exact version</em> of 3SUM with complexity <span class="math-container">$O(n^{2-\varepsilon})$</span> for <span class="math-container">$\varepsilon&gt;0,$</span> what would be the impact on the Exponential Time Hypothesis?</p>
<p>Again, not being an expert, I am wondering would the ETH be refuted? Or the strong ETH only? Please feel free to include details that may be &quot;obvious&quot; in your comments and answers.</p>

CC BY-SA 4.0
2020-07-12T06:32:31.077Z
The answers are great, I just want to add one more comment. If you were able to solve k-SUM in (for example) n^(k/log log log log k + O(1)} time (for k as some slow-growing function of n) then ETH would indeed be false. This result appears in M. Patrascu and R. Williams, SODA 2010.
Ryan Williams
<cc.complexity-theory><ds.algorithms><time-complexity>
Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis
kodlu
# Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis

(Asked by: username_0 on 2020-07-11)

In the recent question [3SUM Complexity—A special(?) Case](https://cstheory.stackexchange.com/questions/47186/3sum-complexity-a-special-case) I asked about why the set size $O(n^3)$ was an interesting value for the 3SUM Problem and got a nice answer. My reference was the paper “Consequences of Faster Alignment of Sequences” by
Abboud, Vassilevska Williams, and Weimann available [here][1]. The term *of a certain size* in the title of this question refers to the support set being $\{-n^3,\ldots,n^3\}$:

**Conjecture 1 (3-SUM Conjecture)** *In the Word RAM model with words of $O(\log n)$ bits, any algorithm requires $n^{2−o(1)}$ time in expectation to determine whether three sets
$A,B,C \subset \{−n^3,\ldots,n^3\}$ with $|A| = |B| = |C| = n$
integers contain three elements $a∈A,b∈B,c∈C$ with $a+b+c=0.$*

If there was an algorithm solving *this exact version* of 3SUM with complexity $O(n^{2-\varepsilon})$ for $\varepsilon>0,$ what would be the impact on the Exponential Time Hypothesis?

Again, not being an expert, I am wondering would the ETH be refuted? Or the strong ETH only? Please feel free to include details that may be "obvious" in your comments and answers.

**Tags:** cc.complexity-theory, ds.algorithms, time-complexity
> **Comments:**
> **username_1**: The answers are great, I just want to add one more comment. If you were able to solve k-SUM in (for example) n^(k/log log log log k + O(1)} time (for k as some slow-growing function of n) then ETH would indeed be false. This result appears in M. Patrascu and R. Williams, SODA 2010.  

---

## 2 answers

### Answer by username_3 on 2020-07-11. Score: 9 | Accepted answer

I think currently it is not even known if strong ETH and 3SUM are related, see e.g. [1]. For the relation of ETH and 3SUM, note that ETH really cannot be refuted by improving polynomial time algorithms (at least via Karp reductions) because it would only improve constants in the exponent of the runtime. In particular, if we reduce 3-SAT to a 3SUM instance of size $2^{O(n)}$, it will not refute ETH, and if we reduce 3-SAT to a 3SUM instance of size $2^{o(n)}$, it will refute ETH regardless of the complexity of 3SUM.

[1] Virginia V. Williams. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). IPEC 2015. <https://drops.dagstuhl.de/opus/volltexte/2015/5568/pdf/5.pdf>


---

### Answer by username_2 on 2020-07-11. Score: 4

The following excellent video:

<https://www.youtube.com/watch?v=YRiyqc99kd0&t=2661s>

and this one:

<https://www.youtube.com/watch?v=x-HskkxUuVI&t=1965s>

Deals with this issue and Fine Grained Approach to Complexity in general.


---

