June 21, 2024
By Patricia Waldron
The Association for Computing Machinery (ACM) has recognized two faculty members and two alumni of the Cornell Ann S. Bowers College of Computing and Information Science with Symposium on Theory of Computing (STOC) Test of Time Awards, given at STOC 2024 in Vancouver, June 24-28.
David Williamson, professor in the School of Operations Research and Information Engineering in Cornell Engineering and in the Department of Information Science received the 30-year Test of Time Award. Jon Kleinberg ’93, the Tisch University Professor of Computer Science, received the 20-year Test of Time Award.
ACM gives three Test of Time Awards annually for papers presented at least 10, 20, or 30 years prior at previous STOC conferences. The selected papers each have had a long-term impact, such as opening a new area of research, establishing a new technique, or solving a problem with enduring importance.
Williamson accepted the award along with his Ph.D. advisor, Michel Goemans at MIT for their 1994 paper, "878-Approximation Algorithms for MAX CUT and MAX 2SAT." They provided "an elegant and highly impactful" algorithm to produce near-optimal solutions to the Max-Cut problem, a central problem in combinatorial optimization. The techniques introduced in the paper, including the use of semidefinite programming, have had a significant and lasting effect in theoretical computer science and optimization theory. The pair also received the 2022 Steele Prize for the same paper. Over time, these findings have yielded applications in a range of fields, including complexity theory, cryptography, combinatorics, and algebra.
"It is amazing to me to see how our paper has continued to have impact on the field over the last 30 years," Williamson said. "I am deeply honored to receive this Test of Time Award with Michel and thank the award committee for selecting our paper."
Kleinberg's "path-setting" paper, "The Small-World Phenomenon: An Algorithmic Perspective," published in 2000, adds an algorithmic dimension to earlier experiments by Stanley Milgram on the small-world phenomenon – the idea that two individuals in a large network are connected by a small number of contacts. The ACM wrote that his paper "gave rise to a deep and rich literature exploring this phenomenon in far more general and practically relevant settings."
Alumni Anirban Dasgupta, Ph.D. '05, and Ravi Kumar, Ph.D. '15, received a 10-year Test of Time Award for their paper with Tamás Sarlos, “A Sparse Johnson-Lindenstrauss Transform,” published in 2010. This paper "gave a rigorous theoretical basis for a widely employed technique in machine learning," wrote the prize committee.
In other alumni news, Ryan Williams '01, M.Eng. '02, has won the 2024 Gödel Prize for his paper "Non-Uniform ACC Circuit Lower Bounds." Given annually since 1993, the Gödel Prize honors outstanding papers in the area of theoretical computer science.
Patricia Waldron is a writer for the Cornell Ann S. Bowers College of Computing and Information Science.