## [Computational Complexity] A nice result, but not good for...

Expand Messages
• 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
Message 1 of 1 , Aug 22 8:43 AM
• 0 Attachment

When people ask you if theory is practical you should give them a problem that
1. People actually want to solve.
2. The algorithm and lower bound for it are relevant at reasonable sizes of the input.
3. The algorithm for it can be implemented and perhaps actually has been.
Is there a result that fails on all three? That is, is there a result that
1. People do not care about solving.
2. The best known algorithm/lower bound only apply when the size of the input is astronomical.
3. The algorithm for it cannot be implemented.
I have one in mind. It is from an excellent paper by Alon and Azar: Finding an Approximate Maximum
1. 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?
2. Let r(n) be the number of rounds. They proved log* n - 4 &le r(n) &le log* n + 2.
3. The algorithm uses a certain type of expander graph. They prove this type exists by prob method, so the proof is nonconstructive.
I like this result alot! I like having very close upper and lower bounds and the proofs are nice. Gives a nice application of a simple type of expander graph! However, I would not use it to convince someone that theory is practical.

--
Posted By GASARCH to Computational Complexity at 8/22/2008 10:42:00 AM
Your message has been successfully submitted and would be delivered to recipients shortly.