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.
$\begingroup$
$\endgroup$
2
-
9$\begingroup$ In what computational model? $\endgroup$– Mahdi CheraghchiOct 11, 2011 at 5:28
-
$\begingroup$ Good point. I meant the comparision based model. $\endgroup$– Vinayak PathakOct 11, 2011 at 19:39
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
Ben-Or 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.
-
3$\begingroup$ irrelevant aside: the first three are also the canonical hard problems for communication-complexity-based stream algorithm lower bounds. $\endgroup$ Oct 11, 2011 at 14:01
-
$\begingroup$ @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? $\endgroup$ Oct 11, 2011 at 19:42
-
1$\begingroup$ 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 $\endgroup$ Oct 11, 2011 at 20:14