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

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