Constants matter

décembre, 19, 2009
Sylvain

Today I am writing a very small post to encourage you (my beloved readers) to directly go to Richard Lipton’s blog to read this very good post The 3 percent solution.
Richard Lipton (professor of Computer Science at Georgia Tech) is talking about a question that arises in its mind about the role of theory w.r.t. real world problems.

Indeed, using again and again \cal O notation to assess the interest of our work, don’t we loose something? I often tell to my students that the choice of a sorting algorithm in practice does not only depend on the asymptotic complexity, but also on the value of the constants w.r.t. the predicted size of the inputs. In practice it could be of interest to find subtle tricks that lower these constants. This is the issue that Lipton discusses, asking this: « Can we apply our algorithmic tricks to get small percent increases that really matter? Would papers on this type of work be accepted at our top conferences? Would NSF fund this type of research? Are there models of how we can help in this way?« 

Unfortunately, my guess is that the answers are yes, no, no and maybe yes.

One Response to “Constants matter”

Thanks for pointer. I agree with you comments completely.

dick lipton

dick lipton, 19 décembre 2009 à 20:21
Picture: courtesy of Abby Blank