Cornell Bowers College of Computing and Information Science
The faces of two men superimposed over a stylized network

Story

Williamson and Kleinberg receive Test of Time Awards at STOC 2024

June 21, 2024

By Patricia Waldron

The Association for Computing Machinery (ACM) has recognized two faculty members in the Cornell Ann S. Bowers College of Computing and Information Science with Symposium on Theory of Computing (STOC) Test of Time Awards, which will be given at STOC 2024 in 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 has been selected for the 30-year Test of Time Award. Jon Kleinberg, ’93, the Tisch University Professor of Computer Science, has been chosen for 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 have each 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 will receive 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." 

Patricia Waldron is a writer for the Cornell Ann S. Bowers College of Computing and Information Science.