By David LaRocca
David Williamson, chair of the Department of Information Science in the Cornell Ann S. Bowers College of Computing and Information Science and professor of Operations Research and Information Engineering (ORIE), will receive the 2022 American Mathematical Society (AMS) Steele Prize for Seminal Contribution to Research for the paper, “Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming.”
In receiving this award, Williamson is joined by his coauthor and mentor, Michel X. Goemans, RSA Professor of Mathematics at the Massachusetts Institute of Technology. “I'm very honored to be the co-winner of the Leroy P. Steele Prize with my Ph.D. advisor, Michel Goemans,” Williamson noted. “Let me express my gratitude to the selection committee for choosing our paper for the prize.”
The paper, published in 1995 in the Journal of the ACM, focuses on the Max‐Cut problem — a core problem in combinatorial optimization — and has had a major, sustained impact on the fields of theoretical computer science and optimization theory.
In their seminal work, Williamson and Goemans presented a new approximation algorithm for the Max‐Cut problem that yields an approximation ratio of 0.878. The algorithm introduced several key innovations that have become classic. This result and the systematic analysis procedure had an immediate and major influence; for instance, many related NP‐hard problems (i.e., nondeterministic polynomial time) were studied via relaxation to semidefinite programs and approximation ratios were established and characterized for many problems. Moreover, as time passed, their findings have become applicable to an even wider range of fields, with connections to complexity theory, cryptography, combinatorics, and algebra.
“Michel and I worked out the idea of representing a cut by vectors and relaxing these to a semidefinite program during my years in graduate school,” said Williamson. “But it was only after I had turned in my thesis that we hit on the idea of using a random hyperplane to partition the vectors. The analysis of the main result quickly followed.”
Williamson was born in Madison, Wis., but grew up in the suburbs of Honolulu, Hawai‘i. Upon receiving his Ph.D. in computer science from MIT in 1993, Williamson was a postdoc at Cornell under Professor Éva Tardos. In 1995, he became a research staff member for IBM Research at the T. J. Watson Research Center in Yorktown Heights, N.Y. and from 2000 to 2003, he was senior manager of the Computer Science Principles and Methodologies group at IBM’s Almaden Research Center in San Jose, Calif. In 2004, Williamson returned to Cornell as a professor with a joint appointment in the School of Operations Research and Information Engineering (ORIE) and the Department of Information Science. In 2021, he was appointed chair of the Department of Information Science.
Well-known for his work in the area of discrete optimization, his research focuses on finding efficient algorithms for hard discrete optimization problems, with attention to approximation algorithms for problems in network design, facility location, and scheduling.
Williamson is a coauthor of the book, “The Design of Approximation Algorithms,” published by Cambridge University Press and winner of the 2013 INFORMS Lanchester Prize. His Ph.D. dissertation on designing low-cost survivable networks was awarded several prizes, including the 1994 Tucker Prize from the Mathematical Programming Society. His work with Michel Goemans on the uses of semidefinite programming has also been awarded several prizes, including the 2000 Fulkerson Prize from the Mathematical Programming Society and the American Mathematical Society. He has served as an associate editor on several journals and was the editor-in-chief of the SIAM Journal on Discrete Mathematics. For his many contributions, he has been recognized as an ACM Fellow and a SIAM Fellow.
The Steele Prize for Seminal Contribution to Research is awarded for a paper that has proved to be of fundamental or lasting importance in its field, or a model of important research. The prize is awarded according to the following six-year rotation of subject areas: open, analysis/probability, algebra/number theory, applied mathematics, geometry/topology, and discrete mathematics/logic. The Steele Prizes were established in 1970 in honor of George David Birkhoff, William Fogg Osgood, and William Caspar Graustein, and are endowed under the terms of a bequest from Leroy P. Steele.
The 2022 prize will be presented during the Joint Prize Session at the 2022 Joint Mathematics Meetings later this year.