Allen School professor Thomas Rothvoss has carved a career out of complexity. As a member of the school’s Theory of Computation Group, Rothvoss examines the theoretical limits of computer algorithms that are designed to analyze large, complex datasets. His aim is to settle long-standing problems in the field of combinatorial optimization — an area where he has made notable progress since his arrival at the University of Washington in 2014.
“I work in theoretical computer science and discrete optimization,” said Rothvoss, who also holds the Craig McKibben and Sarah Merner Professorship in the UW Department of Mathematics. “Over the years my focus has changed a bit. During my Ph.D., I worked on approximation algorithms which deal with finding provably good solutions to NP-hard problems in polynomial time. Later, I moved more towards discrepancy theory and theoretical aspects of linear and integer programming.”
Last month, Rothvoss collected the inaugural Trevisan Prize in the mid-career category for his breakthrough contributions in the study of optimization problems. The award, which is sponsored by the Bocconi University Department of Computing Sciences and the Italian Academy of Sciences, is named for the late Luca Trevisan in recognition of his major innovations to computing theory.
Rothvoss’ own list of innovations includes a new approximation algorithm for solving the bin-packing problem in polynomial time, one of computer science’s classical combinatorial optimization problems. In the bin-packing problem, the goal is to find the fewest number of identical bins that can hold a list of items, without exceeding each bin’s capacity. By leveraging a combination of a novel two-stage packing method — where first they pack items into containers and then put those containers into bins — and making use of discrepancy theory techniques, Rothvoss and his former UW Department of Mathematics Ph.D. student and current postdoc Rebecca Hoberg introduced an algorithm that achieves an additive gap of only O(log OPT) bins, significantly improving on previous results. The paper received the Best Paper Award at the 25th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014).
He was also recognized for his work addressing another open question central to the field of combinatorial optimization. Multiple authors had already established that various polytopes have exponential extension complexity for NP-hard problems. However, Rothvoss wanted to see if the same was true for polytopes that admit polynomial time algorithms to optimize linear functions. In a paper titled “The matching polytope has exponential extension complexity,” Rothvoss was able to prove that linear programming cannot be used to solve the matching problem in polynomial time, advancing theoreticians’ understanding of the topic. He earned both the 2018 Delbert Ray Fulkerson Prize and the 2023 Gödel Prize for the work — the former honoring exceptional papers in discrete mathematics, the latter for outstanding papers in theoretical computer science
More recently, Rothvoss and his former Ph.D. student Victor Reis (Ph.D. ‘23) utilized geometric tools to develop a faster new algorithm for solving integer programming problems within a fixed set of variables. Integer programming is used for optimizing problems with whole number amounts, but many of the algorithms previously introduced for these types of problems have been quite slow based on the number of steps required. Instead, the researchers resolved a version of the Subspace Flatness Conjecture, and proved a new upper bound on the time required to solve for any integer program. While the breakthrough is theoretical, the research has opened up new questions for theoreticians to pursue, earning Rothvoss a Best Paper Award at the 64th IEEE Symposium on Foundations of Computer Science (FOCS 2023).
In addition to the Trevisan Prize, Rothvoss has been a recipient of a National Science Foundation CAREER Award, David and Lucile Packard Foundation Fellowship and a Sloan Research Fellowship.
Read more about the Trevisan Prize winners.