Meet the 2012 MacArthur Fellows
macfound.org
macfound.org
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.
[Edit to fix my silly typo]
Him and the band playing Bach on bluegrass instruments. http://www.youtube.com/watch?v=p1NNBf7uVQ4
Him and the band playing Reptilia. http://www.youtube.com/watch?v=qayc6yJXG-8
Covering Radiohead, then transition into a Gillian Welch song. http://www.youtube.com/watch?v=igbbbWqDVbM
And there's a lot of original compositions as well.
Pretty unstoppable.
Daniel Spielman, Yale University Professor