Thomas Rothvoss

Associate 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:
  • 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:
  • Victor Reis
  • Yihao Zhang
Graduated Ph.D.:
  • Sami Davies (2021).
  • Harishandra Ramadas (2017).
  • Rebecca Hoberg (2017).
Graduated Ms.:
  • Elaine Levey

Awards

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

  • 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-..)
  • 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:
    • STOC 2022
    • SODA 2022
    • ESA 2020
    • FOCS 2018
    • FOCS 2015
    • SODA 2015
    • ESA 2015
    • WAOA 2015
    • APPROX 2014
    • WAOA 2014

Publications (chronologically):