<p><a href="http://www.cse.huji.ac.il/~benor/AlgCompTrees83.pdf">Ben-Or</a> directly proved  $\Omega(n\log n)$ lower bounds for several fundamental problems in the algebraic computation tree model:</p>

<ul>
<li>Element distinctness: Given an array of $n$ real numbers, are its elements distinct?</li>
<li>Set disjointness: Given two sets of $n$ real numbers, do they have an element in common?</li>
<li>Set equality: Given two sets of $n$ real numbers, is one array a permutation of the other?</li>
<li>Measure problem: Given $n$ real intervals, what is the total length of their union?</li>
<li>Set inclusion: Given two sets of real numbers, is one a subset of the other?</li>
<li>Permutation Parity: Given an permutation of the set $[n]$, is the permutation even or odd?</li>
</ul>

<p>The first three are the ones most often used in computational geometry.</p>

CC BY-SA 3.0
2011-10-11T14:01:52.010Z
irrelevant aside: the first three are also the canonical hard problems for communication-complexity-based stream algorithm lower bounds.
Suresh Venkat
CC BY-SA 3.0
2011-10-11T19:42:15.037Z
@SureshVenkat - I have seen set disjointness and set equality being used for proving lower bounds in streaming. Do you have an example for element distinctness?
Vinayak Pathak
CC BY-SA 3.0
2011-10-11T20:14:51.010Z
At least one place I saw it was in the analysis of algorithms under the W-stream model. In general, ED is closely related to bit-vector (or set) disjointness
Suresh Venkat
CC BY-SA 3.0
2011-10-11T09:08:34.730Z
2011-10-11T09:08:34.730Z
Jeffε
<p>What are the standard problems we can reduce from to prove $\Omega(n\log n)$ lower bounds?</p>

<p>Of course, state problems other than sorting and element distinctness. </p>

CC BY-SA 3.0
2011-10-11T05:28:28.760Z
In what computational model?
Mahdi Cheraghchi
CC BY-SA 3.0
2011-10-11T19:39:11.747Z
Good point. I meant the comparision based model.
Vinayak Pathak
<cc.complexity-theory><lower-bounds>
Problems to reduce from to prove an $\Omega(n\log n)$ lower bound
Vinayak Pathak
# Problems to reduce from to prove an $\Omega(n\log n)$ lower bound

(Asked by: username_0 on 2011-10-11)

What are the standard problems we can reduce from to prove $\Omega(n\log n)$ lower bounds?

Of course, state problems other than sorting and element distinctness.

**Tags:** cc.complexity-theory, lower-bounds
> **Comments:**
> **username_1**: In what computational model?  
> **username_0**: Good point. I meant the comparision based model.  

---

## 1 answers

### Answer by username_2 on 2011-10-11. Score: 18 | Accepted answer

[Ben-Or](http://www.cse.huji.ac.il/~benor/AlgCompTrees83.pdf) directly proved $\Omega(n\log n)$ lower bounds for several fundamental problems in the algebraic computation tree model:

* Element distinctness: Given an array of $n$ real numbers, are its elements distinct?
* Set disjointness: Given two sets of $n$ real numbers, do they have an element in common?
* Set equality: Given two sets of $n$ real numbers, is one array a permutation of the other?
* Measure problem: Given $n$ real intervals, what is the total length of their union?
* Set inclusion: Given two sets of real numbers, is one a subset of the other?
* Permutation Parity: Given an permutation of the set $[n]$, is the permutation even or odd?

The first three are the ones most often used in computational geometry.

> **Comments:**
> **username_3**: irrelevant aside: the first three are also the canonical hard problems for communication-complexity-based stream algorithm lower bounds.  
> **username_0**: @SureshVenkat - I have seen set disjointness and set equality being used for proving lower bounds in streaming. Do you have an example for element distinctness?  
> **username_3**: At least one place I saw it was in the analysis of algorithms under the W-stream model. In general, ED is closely related to bit-vector (or set) disjointness  

---

