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)

### 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