ORIE Professor David Williamson and MIT’s Michel Goemans will receive the 2022 AMS Steele Prize for Seminal Contribution to Research for their paper "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming," published in 1995 in the Journal of the ACM. This paper, which focuses on the Max-Cut problem, a core problem in combinatorial optimization, has had major, sustained impact on the fields of theoretical computer science and optimization theory.
“I'm very honored to be the co-winner of the Leroy P. Steele Prize with my Ph.D. advisor, Michel Goemans,” said Williamson.
In their seminal work, Goemans and Williamson 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 impact—many related NP‐hard problems were studied via relaxation to semidefinite programs and approximation ratios were established and characterized for many problems. Moreover, over time, the result has grown in centrality and importance, 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,” Williamson said. “But then we got stuck on the question of how to extract a cut from the vectors, and we shelved the work for at least a year while I finished up my dissertation on an entirely different topic. I turned in my thesis and took a two-week vacation. On my return, we picked up the pieces again and during a two-hour meeting one Friday afternoon we hit on the idea of using a random hyperplane to partition the vectors. The analysis of the main result quickly followed. I sometimes tell my students (and myself) this story to explain why persistence is important and why one shouldn't give up too quickly on one's ideas.”
Professor Williamson is the chair of the Department of Information Science at Cornell University, and a professor in the School of Operations Research and Information Engineering. He received his Ph.D. in computer science from MIT under Professor Goemans in 1993. After a postdoc at Cornell under Professor Éva Tardos, he was a research staff member for IBM Research at the T.J. Watson Research Center in Yorktown Heights, NY. From 2000-03, he was the Senior Manager of the Computer Science Principles and Methodologies group at IBM’s Almaden Research Center in San Jose, CA. He moved to Cornell University in 2004.
Professor Goemans is the RSA Professor in the Department of Mathematics at MIT and currently head of the department. Born in Belgium, he did his undergraduate studies at the University of Louvain (Belgium) in applied mathematics and his graduate studies at MIT. From 1997-99, he held a professorship at UCLouvain while on leave from MIT. At MIT, he was the Robert E. Collins Distinguished Scholar in Mathematics in 2006-2007 and held the Leighton Family Professorship in Mathematics from 2007 to 2017. He has had an adjunct professorship at the University of Waterloo, Ontario, Canada, and a visiting professorship at RIMS, Kyoto, Japan.
The Steele Prize for Seminal Contribution to Research is awarded for a paper, whether recent or not, 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 Wednesday, January 5 during the Joint Prize Session at the 2022 Joint Mathematics Meetings in Seattle.
Data science, molecular mechanisms, unconventional computing for optimization and machine learning, wave interaction with engineered materials, electrocatalysis, and compound semiconductor devices are... Read more about Data science, wave interaction, semiconductors earn engineering research awards
Earlier this year, Cornell Tech Dean Greg Morrisett announced that a gift from Howard Morgan Ph.D. ’68 and his wife Eleanor, will be used to endow a new faculty chair—the Howard and Eleanor Morgan... Read more about New gift endows Morgan Chair to ORIE's Topaloglu
David Williamson, professor in the School of Operations Research and Information Engineering and in the Department of Information Science, has agreed to extend his appointment as Chair of the Department of Information Science, a role he has held since July 1, 2021, for an additional year. Read more about David Williamson extends IS chair appointment
