3 ms·
Yea, Daniel Spielamn and Shang-Hua Teng won the Gödel Prize for their work on smoothed analysis of simplex algorithms. They introduced a way to formally study t
by isaacfung 3y ago
Yea, Daniel Spielamn and Shang-Hua Teng won the Gödel Prize for their work on smoothed analysis of simplex algorithms. They introduced a way to formally study the worst case complexity of algorithms when the inputs are randomly perturbed by a small amount.
https://www.di.ens.fr/~vergnaud/algo0910/Simplex.pdf https://www.di.ens.fr/~vergnaud/algo0910/Simplex.pdf
- pfdietz 3y agoSpielman in 2013 also (with Adam Marcus and Nikhil Srivastava) came out of left field and solved the long open Kadison-Singer problem, to the surprise of more mainstream mathematicians. I find this interplay between "traditional" mathematicians and those in allied fields like CS to be very interesting.