When people ask you if theory is practical you should give them a problem that
- People actually want to solve.
- The algorithm and lower bound for it are relevant at reasonable sizes of the input.
- The algorithm for it can be implemented and perhaps actually has been.
- People do not care about solving.
- The best known algorithm/lower bound only apply when the size of the input is astronomical.
- The algorithm for it cannot be implemented.
- The problem is, given n numbers, find some number in the top half (that is max or 2nd largest or 3rd largest or ... or median). The model is parallel: we get to make n comparisons per round. The question is: How many rounds does it take?
- Let r(n) be the number of rounds. They proved log* n - 4 &le r(n) &le log* n + 2.
- The algorithm uses a certain type of expander graph. They prove this type exists by prob method, so the proof is nonconstructive.