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.

Lecture notes and expositions

Students

Current PhD advisees:
  • Rainie Heck
  • Sally Dong
Graduated Ph.D.:
  • Victor Reis (2023)
  • Yihao Zhang (2022)
  • Sami Davies (2021).
  • Harishandra Ramadas (2017)
  • Rebecca Hoberg (2017)
Graduated Ms.:
  • 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

Professional service

  • Editor for Theory of Computing (TOC) (2019-..)
  • 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:
    • FOCS 2023
    • STOC 2022
    • SODA 2022
    • ESA 2020
    • FOCS 2018
    • FOCS 2015
    • SODA 2015
    • ESA 2015
    • WAOA 2015
    • APPROX 2014
    • WAOA 2014

Publications (chronologically):