Dan Spielman wins the 2021 STOC Test of Time Award

June 24, 2021

Daniel A. Spielman and Shang-Hua Teng have won the 20-year STOC Test of Time Award for their paper “Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time”, STOC 2001.

The Spielman-Teng paper introduced the smoothed analysis of algorithms, a hybrid between worst-case and average-case analysis, and showed that the classical Simplex algorithm for Linear Programming has polynomial smoothed complexity (even though its worst case complexity is exponential). Smoothed analysis has been applied subsequently to a number of other algorithms for various problems, providing a way to go beyond traditional worst-case analysis and explain rigorously their performance in practice.

The 2021 STOC Test of Time Award recognizes papers published in the Proceedings of the Annual ACM Symposium on Theory of Computing. The award was inaugurated in 2021 and will be given annually thereafter. There are three awards, targeting the STOC conferences 10, 20, and 30 years prior to the year in which the award is given.