The only person on the list whose work I'm somewhat aware of is Dan Spielman. His works, especially smoothed analysis, is definitely something that HN folks wil

The only person on the list whose work I'm somewhat aware of is Dan Spielman. His works, especially smoothed analysis, is definitely something that HN folks will appreciate. Smoothed analysis answers the question why many popular algorithms have exponential big-O time but still work so well in practice. Average case complexity also answers that question but computing it requires us to know the probability distribution of the input space in advance. The idea of smoothed complexity is simply to add random perturbation to the input and then measure the worst case. Eg. simplex method has exponential big-O complexity but polynomial smoothed complexity.