Friday, August 22, 2008

A nice result, but not good for...



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.
at

6 comments:

  1. Anonymous11:04 AM, August 22, 2008

    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.

    ReplyDelete
  2. Anonymous12:49 PM, August 22, 2008

    The result may not be important, but how about the techniques...?

    =)

    ReplyDelete
  3. Anonymous3:36 PM, August 22, 2008

    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.

    Consider 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.

    ReplyDelete
  4. Anonymous1:01 AM, August 24, 2008

    "When people ask you if theory is practical ..."

    ... 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?

    ReplyDelete
  5. Louis Wasserman10:46 PM, August 25, 2008

    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.

    ReplyDelete
  6. Arindam11:49 AM, August 28, 2008

    Why 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