Thomas Rothvoss

Craig McKibben and Sarah Merner Professor
Department of Mathematics
Paul G. Allen School of Computer Science and Engineering
University of Washington, Seattle

Diploma at TU Dortmund (2006); PhD at EPFL (2009);
PostDoc at EPFL (2010); PostDoc at MIT (2011-2013)

I am part of the UW CS theory group and the Optimization group.

### Research

I work in the intersection of theoretical computer science and discrete mathematics. In particular, currently I am interested in approximation algorithms, discrepancy theory and related questions in high dimensional convex geometry. Here is some recent work:
• Lattices. In [Reis, R. 2023] we prove that the volume-based lower bound to the covering radius for any lattice w.r.t. any convex body is within a O(log^3 n)  factor of the real covering radius. This implies that integer programs with n variables can be solved in time (log n)^O(n).
• Convex geometry. Schechtman posed the question whether the vector balancing constant of any d-dimensional zonotope is O(d^1/2). In [Heck, Reis, R 2022] we prove a bound of O(d^1/2 * log log log d) matching the conjectured bound up to a miniscule triple log factor.
• Approximation algorithms. For many problems, the naive linear programming relaxation is too weak to find good approximations. The Sherali-Adams / Lasserre lift then provides a systematic strengthening. For example in [Davies et al. FOCS 2020] we can use this method to obtain a O(log^2 n)-approximation for scheduling with precedence constraints and communication delays.
• Discrepancy theory. In the geometric setting of discrepancy theory, one has a concrete symmetric convex body K and asks for a minimal scaling of s > 0, so that the body sK contains a vector with {-1,+1} entries. In [Reis, R. SODA 2020], we considered the body K arising from balancing matrices w.r.t. the operator norm and prove that it must have high mean width. Then this implies a new algorithm to find linear-size spectral sparsifiers in graphs.

### Students

• Rainie Heck
• Sally Dong
• Victor Reis (2023)
• Yihao Zhang (2022)
• Sami Davies (2021).
• Rebecca Hoberg (2017)
• Elaine Levey

### Awards

• FOCS 2023 Best Paper Prize
• Gödel Prize 2023
• IPCO 2023 Best Paper Prize
• Delbert Ray Fulkerson Prize (2018)
• STOC 2014 Best Paper Prize
• SODA 2014 Best Paper Prize
• STOC 2010 Best Paper Prize
• Best Computer Science Graduate at TU Dortmund (2007)

### Selected Funding

• NSF SMALL (2023-2026)
• NSF CAREER grant (2017-2022)
• Packard Foundation Fellowship (2016-2021)
• Sloan Research Fellowship (2015-2017)
• Feodor Lynen post-doctoral fellowship (2011-2012)

### Teaching at the University of Washington

• Fall 2024 - CSE 521 - Design and Analysis of Algorithms (no webpage yet)
• Winter 2024 - CSE 531 - Computational Complexity
• Fall 2023 - Math 514 - Networks and Combinatorial Optimization
• Winter 2023 - CSE599S - Lattices (graduate special topics course)
• Fall 2022 - Math 514 - Networks and Combinatorial Optimization (graduate course)
• Spring 2022 - Math 409 - Discrete Optimization (undergraduate course)
• Spring 2021 - CSE 311 - Foundations of Computing 1 (undergraduate course)
• Winter 2021 - Math 582F - Asymptotic Convex Geometry (graduate special topics course)
• Fall 2020 - Math 514 - Network Optimization (graduate course)
• Spring 2020 - Math 409 - Discrete Optimization (undergraduate course)
• Spring 2019 - CSE 311 - Foundations of Computing 1 (undergraduate course)
• Winter 2019 - Math 582D - Probabilistic Combinatorics (graduate special topics course)
• Winter 2018 - Math 514 - Network Optimization (graduate course)
• Spring 2017 - Math 409 - Discrete Optimization (undergraduate course)
• Winter 2017 - CSE 421 - Introduction to Algorithms (undergraduate course)
• Fall 2016 - Math 514 - Network Optimization (graduate course)
• Spring 2016 - Math 583D -Integer Optimization and Lattices (graduate special topics course)
• Winter 2016 - CSE 421 - Introduction to Algorithms (undergraduate course)
• Spring 2015 - Math 409 - Discrete Optimization (undergraduate course)
• Winter 2015 - Math 126 - Calculus with Analytic Geometry III (undergraduate course)
• Fall 2014 - Math 514 - Network Optimization (graduate course)
• Spring 2014 - Math 126 - Calculus with Analytic Geometry III (undergraduate course)
• Winter 2014 - Math 409 - Discrete Optimization (undergraduate course)

### Professional service

• Editor for Theory of Computing (TOC) (2019+)
• Editor for the Journal of the ACM (2024+)
• Co-organizer for a semester-long program in fall 2017 at the Simons Institute for the Theory of Computing at UC Berkeley
• Conference program committee:
• APPROX 2024
• FOCS 2023
• STOC 2022
• SODA 2022
• ESA 2020
• FOCS 2018
• FOCS 2015
• SODA 2015
• ESA 2015
• WAOA 2015
• APPROX 2014
• WAOA 2014