4 ms·

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 an

by lkozma 16y ago

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 http://en.wikipedia.org/wiki/Smoothed_analysis

bartonfink 16y ago
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?
- lkozma 16y ago
  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. A list of related papers: http://www.cs.yale.edu/homes/spielman/SmoothedAnalysis/index.html http://www.cs.yale.edu/homes/spielman/SmoothedAnalysis/index...
- alextp 16y ago
  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 http://weyond.com/www/focs/2010/downloads/1335.f4v

4 ms·

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 an

by lkozma 16y ago

bartonfink 16y ago
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?
- lkozma 16y ago
  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. A list of related papers: http://www.cs.yale.edu/homes/spielman/SmoothedAnalysis/index.html http://www.cs.yale.edu/homes/spielman/SmoothedAnalysis/index...
- alextp 16y ago
  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 http://weyond.com/www/focs/2010/downloads/1335.f4v