Daniel Spielman Wins Test of Time Award

When Daniel Spielman co-authored a paper on Smoothed analysis of algorithms in 2001, it made a big impact on the fields of mathematics and computer science. A new award shows that, 20 years later, it’s just as impressive. 

Spielman, the Sterling Professor of Computer Science, Statistics and Data Science and Mathematics and Applied Mathematics, and his frequent collaborator, Shang-Hua Teng, have won the 20-year STOC Test of Time Award for their paper. The 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.

Their work, introducing “smoothed analysis” as a way to measure the complexity of an algorithm, has been credited with giving a more realistic understanding of how an algorithm will perform. The concept deals with the phenomenon in which some algorithms work better in practice than in theory.

Spielman and Teng, the Seeley G. Mudd Professor of Computer Science and Mathematics at the University of Southern California, have won a number of other awards for their work with smoothed analysis, including the prestigious Gödel Prize in 2008.

The framework of smoothed analysis that they introduced relies on deep mathematical analysis and insight. It’s been crucial to theoretical computer science and other disciplines - since 2001, there’s been a significant amount of research based on it.

The paper is considered by those in the field to be critical to the grand challenge of developing ways to predict the performance of algorithms and heuristics on real data and on real computers.