Is Smoothed Analysis used outside academia?

Question

Did the smoothed analysis find its way into main stream analysis of algorithms? Is it common for algorithm designers to apply smoothed analysis to their algorithms?

Answer 1

I could be wrong, but I view smoothed analysis as a way to explain the in-practice behaviour of algorithms that have bad theoretical guarantees (simplex, k-means, and so on). I'm not sure what it would mean to use smoothed analysis in practice, except to justify the use of a particular heuristic with bad worst-case performance ("My heuristic has blah blah worst-case behaviour but a smoothed analysis indicates that it will do well in practice etc etc")

Answer 2

The way people analyze algorithms in the real world is vastly different from academia. While in academia the goal is to find a provably-correct upper bound on the running time, in real life the goal is to understand how the algorithm works, and what tweaks can improve the running time. There are two main methods that are banned in academia but used in practice:

• The method of approximation. Here you use a lot of simplifying assumptions to try to forecast the running time of an algorithm. Similar to what theoretical physicists (used to) do.
• Experimentation. You run your algorithm and measure several statistics - how much time went to each part, how many times each function was called, how often was each branch run, and so on. This information can be used to optimize the algorithm. Experimentation is also used to find out whether some approximations done while analyzing the algorithm work in practice or not.

That said, I don't think that it's very common to analyze an algorithm in practice, other than to add some filler text in a related academic publication. The focus is either on software engineering or on low-level optimization, depending on the subject matter.

Finally, smoothed analysis is a heuristic that can be used to explain why algorithms work better in practice than their worst case would suggest - namely since some of the inputs are "random" in some sense. This heuristic can be used to approximate the behavior of the algorithm if one is using the method of approximation.