Hacker News Reader

Comment by lkozma | Hacker News Reader

A good part of the presentation is a critique of worst-case-analysis, which is often not relevant for practical problems. The author doesn't mention smoothed analysis which addresses this very issue: http://en.wikipedia.org/wiki/Smoothed_analysis

View on HN

That's interesting. I hadn't run into this before in college or grad school, and it seems like a good way of bridging the analytical gap between theory and practice that Sedgewick talked about.

It's unlikely that Sedgewick hadn't heard of this before. I suspect that he didn't mention it simply because it isn't often taught. According to your citation, it was introduced in 2001 which is quite recent in academic terms. How did you come across it?

Yes, it is quite interesting, and although the main idea is straightforward, the analysis of concrete algorithms gets quite technical. Also, it's still actively researched and maybe not entirely accepted into the mainstream yet. AFAIK it has been successfully applied to many well-known algorithms which have bad worst-case, but surprisingly good behavior in practice (e.g. quicksort). I heard about it from my advisor.

Spielman and Teng are very famous, and have received even a Godel prize for their work in smoothed analysis. Currently they're doing some very interesting things with efficient algorithms on graphs laplacians and linear systems, you can see Spielman's talk at last FOCS, it's very enlightening: http://weyond.com/www/focs/2010/downloads/1335.f4v

Reply on news.ycombinator.com