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.
Using some known results, they also give an explicit way of doing it in log*(n)+12 rounds. So , although not as good as the theoretical bound, it is pretty close too.
ReplyDeleteThe result may not be important, but how about the techniques...?
ReplyDelete=)
I'm not sure I would say that log*(n)+12 is really very close to log*(n)+2, given how slowly log*(n) grows.
ReplyDeleteConsider how big n can be for a given number of rounds. The explicit algorithm can't do anything with less than twelve rounds (and needs a few more to do anything useful). The implicit algorithm with the same number of rounds can do n so large it makes astronomical numbers look very small indeed.
"When people ask you if theory is practical ..."
ReplyDelete... is it not a good idea to ask them what they exactly mean by practical? I think such a discussion would be more productive / educational for both parties involved in the discussion, rather than the naive "here's a great counterexample that shows the glorious glorious qualities of theory" response?
Perhaps this (what was mentioned in the blog) kind of thinking is another sign of where theory folks are going wrong: they are agreeing to the premise of all the anti-theory arguments and trying to respond to them, whereas we could perhaps question such faulty premises instead and achieve a better result. No?
Certain results are interesting for purely philosophical reasons -- e.g. quantum computing results, or other discussions that have to do with the nature of our universe. Alternatively, P=BPP unless E has subexponential circuits is a really seriously interesting result in a philosophical sense; the relationship of nonuniform computing to randomness is really kinda neat. Those aren't algorithms, but I would argue to a non-theorist that results like that are seriously interesting on their own merits, without application.
ReplyDeleteWhy do you have to convince people that theory is practical? When people say they believe in God, do they give reasons for such beliefs? Theory is second to none, including God. We don't need to be apologetic for doing math. We will do it anyway.
ReplyDelete