Yin Tat Lee (left) and Thomas Rothvoss
Professors Yin Tat Lee and Thomas Rothvoss of the Allen School’s Theory of Computation group were recently recognized for significant contributions to the field of mathematical optimization. Lee, who joined the University of Washington faculty last year, received the A.W. Tucker Prize recognizing the best doctoral thesis in optimization in the past three years. Rothvoss, who holds a joint appointment in the Allen School and the Department of Mathematics, earned the Delbert Ray Fulkerson Prize recognizing outstanding papers in the area of discrete mathematics.
Lee received the Tucker Prize from the Mathematical Optimization Society for his thesis, “Faster Algorithms for Convex and Combinatorial Optimization,” completed while he was a Ph.D. student at MIT. In that paper, Lee explored how combining and improving upon existing optimization techniques such as sparsification, cutting, and collapsing could yield faster algorithms for solving a variety of problems underpinning the theory and practice of computer science. His research generated a number of substantial advancements, including faster algorithms for solving important problems in linear programming, convex programming, and maximum flow. Lee’s work was significant not only for its practical contributions, but also for its philosophical; whereas researchers historically have tended to study continuous optimization and combinatorial – or discrete – optimization in isolation, Lee recognized that the two areas share some difficulties and could benefit from some of the same techniques. His results earned him MIT’s George M. Sprowls Award for the best Ph.D. thesis in computer science in 2016.
Yin Tat Lee (left) onstage with Tucker Prize Committee chair Simge Kucukyavuz (center) and Karen Aardal, chair of the Mathematical Optimization Society
Lee’s paper was the culmination of several related lines of research that yielded faster algorithms for a variety of outstanding optimization problems — and yielded Lee and his collaborators numerous conference awards. These included Best Paper at the Symposium on Discrete Algorithms (SODA 2014) for presenting a new algorithm for approximately solving maximum flow problems in near-linear time, and Best Student Paper and Best Paper at the Symposium on Foundations of Computer Science (FOCS 2014) for a new general interior point method for solving general linear programs that represented the first significant improvement in the running time of linear programming in more than two decades. Lee and his colleagues subsequently earned Best Student Paper at FOCS 2015 for devising a faster cutting plane method for solving convex problems in near-cubic time.
Since his arrival at the Allen School, Lee has continued to push the state of the art, earning a CAREER Award from the National Science Foundation to further advance his efforts to develop faster, more efficient algorithms for solving convex and other optimization problems. He recently co-authored a total of six papers accepted at the Symposium on Theory of Computing (STOC 2018) — a record number of contributions from an individual researcher to the conference in a single year that addressed an array of open problems in algorithmic convex geometry, asymptotic geometric analysis, operator theory, convex optimization, online algorithms, and probability. Since last summer, he has served as co-principal investigator for the Algorithmic Foundations of Data Science Institute (ADSI), which is developing new algorithmic tools to advance the field of data science with a $1.5 million grant from NSF.
Rothvoss was recognized with the Fulkerson Prize, which is co-sponsored by the Mathematical Optimization Society and the American Mathematical Society, for his paper “The Matching Polytope has Exponential Extension Complexity.” In that work, he set out to answer an open question that is central to combinatorial optimization related to the expression of polytopes for solving linear programs. Whereas multiple authors had established that various polytopes have exponential extension complexity for NP-hard problems, Rothvoss was interested in finding out whether the same could be said for polytopes that admit polynomial time algorithms to optimize linear functions. He established that this is, indeed, the case for the perfect matching polytope — proving that linear programming cannot be used to solve the matching problem in polynomial time. It was a significant leap forward in theoreticians’ understanding of this topic, and one which revealed a significant limitation of a technique that has been extremely popular in the field of operations research.
Thomas Rothvoss (second from left) onstage with (left to right) Fulkerson Prize Committee member Martin Grötschel, and chair Karen Aardal and vice chair William Cook of the Mathematical Optimization Society
Rothvoss was previously recognized with a Best Paper Award at STOC 2014 for the same work, which he conducted while he was a postdoctoral researcher at MIT. That same year, he collected a Best Paper Award at SODA 2014 for his contribution to a new algorithm for solving the bin packing problem in polynomial time. He previously earned Best Paper at STOC 2010 for his work on an approximation algorithm for solving the Steiner tree problem — a particularly important problem in the field of network design. More recently, Rothvoss earned a 2015 Sloan Research Fellowship and a 2016 Packard Fellowship for his work at the intersection of mathematics and computer science to develop new techniques for finding approximate solutions to computationally hard problems.
Last year, Rothvoss earned an NSF CAREER Award for his efforts to design new and better approximation algorithms to address several outstanding problems in combinatorial optimization, including the directed Steiner tree, graph coloring, unique games, and unrelated machine scheduling problems. The goal is to make it more efficient to extract value from vast quantities of data, which will benefit not only computer science but the broader scientific community and a variety of industries. Like Lee, Rothvoss has developed a keen interest in bridging the gap between discrete and continuous optimization, inspired by the emergence of machine learning and massive datasets that have opened up new lines of inquiry at the intersection of those two historically divergent fields. To that end, he co-organized a series of workshops last fall at the Simons Institute for the Theory of Computing that brought together researchers in both communities to stimulate interaction and collaboration on areas of shared interest.
Lee and Rothvoss collected their awards at the 23rd International Symposium on Mathematical Programming (ISMP 2018) last month in Bordeaux, France. ISMP, which is held every three years, is the flagship conference for researchers working in the field of mathematical optimization.
Congratulations, Thomas and Yin Tat!