HTTP/2 200 date: Thu, 01 Jan 2026 09:04:26 GMT server: Apache last-modified: Wed, 22 Oct 2025 20:09:18 GMT etag: "d593-641c4e43487f6" accept-ranges: bytes content-length: 54675 content-type: text/html 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 Analysis of Boolean Functions (lecture notes for a graduate special topics course being held in Fall 2025) Lattices (lecture notes for a graduate special topics course held in Winter 2023) Networks and Combinatorial Optimization (lecture notes for a graduate course held annually) Asymptotic Convex Geometry (lecture notes for a graduate special topics course held in Winter 2021) Probabilistic Combinatorics (lecture notes for a graduate special topics course held in Winter 2019) Integer Optimization and Lattices (lecture notes for a graduate special topics course held in Spring 2016) The Lasserre Hierarchy in Approximation Algorithms (notes for a tutorial held at MAPSP 2013; slides) Discrete optimization (lecture notes for an undergraduate course held annually)

Students Current PhD advisees: Patrick O'Melveny Mathews Boban Graduated Ph.D.: Rainie Heck (2025) Sally Dong (2024; co-advised with Yin Tat Lee) Victor Reis (2023) Yihao Zhang (2022) Sami Davies (2021). Harishandra Ramadas (2017) Rebecca Hoberg (2017) Graduated Master students: Elaine Levey Awards Trevisan Prize 2025 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 2025 - Math 581A - Analysis of Boolean Functions (graduate special topics course) Winter 2025 - Math 409 - Discrete Optimization (undergraduate course) Fall 2024 - CSE 521 - Design and Analysis of Algorithms 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 the Journal of the ACM (2024+) Editor for Theory of Computing (TOC) (2019-2023 Co-organizer for a semester-long program in fall 2017 at the Simons Institute for the Theory of Computing at UC Berkeley Organizer of an Oberwolfach Workshop on "Combinatorial Optimization" in November 2024 Conference program committee: IPCO 2026 STOC 2025 APPROX 2024 FOCS 2023 STOC 2022 SODA 2022 ESA 2020 FOCS 2018 FOCS 2015 SODA 2015 ESA 2015 WAOA 2015 APPROX 2014 WAOA 2014

Publications (chronologically):

• A parameterized linear formulation of the integer hull. F. Eisenbrand, T. Rothvoss. SODA 2026 (to appear). Slides.
• Excluding a Line Minor via Design Matrices and Column Boundsfor the Circuit Imbalance Measure. N. Singer, D. Dadush, F. Eisenbrand, R. Pinchasi, T. Rothvoss. SODA 2026 (to appear).
  
• Tensor Concentration Inequalities: A Geometric Approach. A. Bandeira, S. Gopi, H. Jiang, K. Lucca, T. Rothvoss. STOC 2025.
  See also the math journal version A Geometric Perspective on the Injective Norm of Sums of Random Tensors
• Forall-exist statements in pseudopolynomial time. E. Bach, F. Eisenbrand, T. Rothvoss, Robert Weismantel. SODA 2025.
  
• Optimal Online Discrepancy Minimization. J. Kulkarni, V. Reis, T. Rothvoss. STOC 2024 (see Arxiv 2308.01406). Slides.
  
• Polytopes with Bounded Integral Slack Matrices Have Sub-Exponential Extension Complexity. S. Dong, T. Rothvoss. IPCO 2024.
  
• The Subspace Flatness Conjecture and Faster Integer Programming. V. Reis, T. Rothvoss. FOCS 2023 (best paper award). Arxiv 2303.14605 (2023). Slides. Video.
  A longer version with three 1-hour talks given at Georgia Tech which also covers the Micciancio-Voulgaris algorithm and the Reverse Minkowski Theorem: Slides. Video part 1. Video part 2. Video part 3.
  The paper was cover in Quanta and in  Communications of the ACM.
  
• The Vector Balancing Constant for Zonotopes. L. Heck, V. Reis, T. Rothvoss. Arxiv 2210.16460 (2022)
• From approximate to exact integer programming. D. Dadush, F. Eisenbrand, T. Rothvoss. IPCO 2023 (also Arxiv 2211.03859 and Math Programming B journal version)
  
• Approximate Caratheodory bounds via Discrepancy Theory. V. Reis, T. Rothvoss. Arxiv 2207.03614 (2022).
  
• Approximate CVP in time 2^0.802n -- now in any norm!. T. Rothvoss, M. Venzin. IPCO 2022.
  
• Tight bounds on the Fourier growth of bounded functions on the hypercube. S. Iyer, A. Rao, V. Reis, T. Rothvoss, A. Yehudayoff. To be submitted (2021).
• On the Hardness of Scheduling With Non-Uniform Communication Delays. S. Davies, J. Kulkarni, T. Rothvoss, S. Sandeep, J. Tarnawski, Y. Zhang. SODA 2022.
• Scheduling with Communication Delays via LP Hierarchies and Clustering II: Weighted Completion Times on Related Machines. S. Davies, J. Kulkarni, T. Rothvoss, J. Tarnawski, Y. Zhang. SODA 2021.
  
• Scheduling with Communication Delays via LP Hierarchies and Clustering. S. Davies, J. Kulkarni, T. Rothvoss, J. Tarnawski, Y. Zhang. FOCS 2020.
  
• Vector Balancing in Lebesgue Spaces. V. Reis, T. Rothvoss. Random Structures & Algorithms (to appear; 2022).
  
• A Tale of Santa Claus, Hypergraphs and Matroids. S. Davies, T. Rothvoss,. Y. Zhang. SODA 2020. (see Arxiv 1807.07189., video of the older version with a 6-apx)
• Linear Size Sparsifier and the Geometry of the Operator Norm Ball. V. Reis and T. Rothvoss. SODA 2020 (see Arxiv 1907.02145)
• A Fourier-Analytic Approach for the Discrepancy of Random Set Systems. R. Hoberg, T. Rothvoss. SODA 2019. (see Arxiv ID 1806.04484).
• An improved deterministic rescaling for linear programming algorithms. R. Hoberg and T. Rothvoss. IPCO 2017 (Arxiv).
• Deterministic discrepancy minimization via the multiplicative weight update method. A. Levy, H. Ramadas, T. Rothvoss. IPCO 2017 (Arxiv)
  
• Number Balancing is as hard as Minkowski’s Theorem and Shortest Vector. R. Hoberg, H. Ramadas, T. Rothvoss, X. Yang. IPCO 2017 (Arxiv)
• A Logarithmic Additive Integrality Gap for Bin Packing. R. Hoberg and T. Rothvoss. SODA 2017 (Arxiv ID 1503.08796 from 2015). Slides.
• A (1+ epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies. E. Levey and T. Rothvoss. STOC'16 (Arxiv, slides).
  
• Constructive discrepancy minimization for convex sets. T. Rothvoss. FOCS 2014. Invited to the SICOMP Special Issue for FOCS'14. See also ArXiv ID 1404.0339. Slides. Video.
• The matching polytope has exponential extension complexity. T. Rothvoß. STOC 2014. Winner of the STOC 2014 Best Paper Prize. See also ArXiv ID 1311.2369. Slides. Video.
  
• Polynomiality for Bin Packing with a Constant Number of Item Types. M.X. Goemans and T. Rothvoß. SODA 2014 (Co-winner of Best Paper Award; invited to the Journal of the ACM, see also ArXiv ID 1307.5108. 2013). Slides. Video (talk given by my co-author).
• A direct proof for Lovett's bound on the communication complexity of low rank matrices. T. Rothvoss. Arxiv ID 1409.6366. Slides.
• Approximating Bin Packing within O(log OPT log log OPT) bins. T. Rothvoß. FOCS 2013. Invited to the SICOMP Special Issue for FOCS'13 (see also ArXiv ID 1301.4010. 2013). Slides. Video.
• Steiner Tree Approximation via Iterative Randomized Rounding. J. Byrka, F. Grandoni, T. Rothvoss and L. Sanità. Invited submission to the Journal of the ACM. Journal version of the STOC'10 paper. Slides (short). Slides (long).
• Bin Packing via Discrepancy of Permutations. F. Eisenbrand, D. Palvoelgyi and T. Rothvoß. Invited submission to TALG SODA'11 special issue.
  Remark: This is the journal version of the SODA'11 paper. Since the conjecture of Beck has been disproven few months after SODA'11 by Newman and Nikolov, I recommend to read this journal version instead of the original SODA paper.  
• A simpler proof for O(congestion + dilation) packet routing. T. Rothvoß. IPCO 2013. Slides.
  
• 0/1 Polytopes with Quadratic Chvátal Rank. T. Rothvoß and L. Sanità. IPCO 2013. Slides.
• Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations. M. X. Goemans, N. Olver, T. Rothvoss, R. Zenklusen. STOC'12.
• The Entropy Rounding Method in Approximation Algorithms. T. Rothvoss. Symposium on Discrete Algorithms (SODA 2012), Kyoto, Japan, January 17-19, 2011. Slides (short). Slides (long).
• Extended formulations for polygons. S. Fiorini, T. Rothvoß, H. Raj Tiwary. Discrete & Computational Geometry. 2012.
• Some 0/1 polytopes need exponential size extended formulations. T. Rothvoss. Mathematical Programming. 2012. Slides.
• Cover-Decomposition and Polychromatic Numbers. B. Bollobás, D. Pritchard, T. Rothvoß, A. Scott. 19th Annual European Symposium on Algorithms (ESA 2011), Saarbrücken, Germany, 5.-9. September, 2011. 
• A PTAS for the Highway Problem. F. Grandoni and T. Rothvoß. Symposium on Discrete Algorithms (SODA 2011), San Francisco, USA, January 22-25, 2011. Slides.
• Bin Packing via Discrepancy of Permutations. F. Eisenbrand, D. Palvoelgyi and T. Rothvoß. Symposium on Discrete Algorithms (SODA 2011), San Francisco, USA, January 22-25, 2011. Slides.
• From Uncertainty to Nonlinearity: Solving Virtual Private Network via Single-Sink Buy-at-Bulk. F. Grandoni, T. Rothvoß and L. Sanità. Math. Oper. Res. 36(2): 185-204 (2011).
  Combined journal version of the APPROX'09 and ICALP'10 paper.
• Set Covering with Ordered Replacement: Additive and Multiplicative Gaps. F. Eisenbrand, N. Kakimura, T. Rothvoß, L. Sanità. IPCO 2011.
• Approximation Algorithms for Single and Multi-Commodity Connected Facility Location. F. Grandoni and Thomas Rothvoß. IPCO 2011. Slides.
• Directed Steiner Tree and the Lasserre Hierarchy. T. Rothvoss. ArXiv ID 1111.5473. Slides.
• Diameter of Polyhedra: Limits of Abstraction. F. Eisenbrand, N. Hähnle, A. Razborov and T. Rothvoss. 2010. Journal version of the SOCG'09 paper.
• An Improved LP-based Approximation for Steiner Tree. J. Byrka, F. Grandoni, T. Rothvoß and L. Sanità. 42th ACM Symposium on Theory of Computing (STOC 2010, Best Paper Award), Cambridge, Massachusetts, USA, June 6-8, 2010. Slides.
• A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks. A. Karrenbauer and T. Rothvoss. Approximation and Online Algorithms, 8th International Workshop (WAOA 2010), Liverpool, UK, September 9-10, 2010. Slides.
  
• Network Design via Core Detouring for Problems Without a Core. F. Grandoni and T. Rothvoss. Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010. Slides.
• EDF-schedulability of synchronous periodic task systems is coNP-hard. F. Eisenbrand and T. Rothvoß. ACM-SIAM Symposium on Discrete Algorithms (SODA10), Austin, Texas, January 17-19, 2010. Slides.
• Optimal selection of customers for a last-minute offer. R. Cominetti, J. R. Correa, T. Rothvoß and J. San Martín. Operations Research. 2010.
• Exact quantification of the sub-optimality of uniprocessor fixed-priority pre- emptive scheduling. R. Davis, T. Rothvoß, S. Baruah and A. Burns. Real-time Systems. 2009.
• On the Complexity of the Asymmetric VPN Problem. T. Rothvoß and L. Sanità. 12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization problems (APPROX '09), UC Berkeley, USA, August 21-23, 2009. Slides.
• New Hardness Results for Diophantine Approximation. F. Eisenbrand and T. Rothvoß. 12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX '09), UC Berkeley, USA, August 21-23, 2009. Slides.
  
• An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-time Scheduling. A. Karrenbauer and T. Rothvoß. 17th Annual European Symposium on Algorithms (ESA'09), Copenhagen, September 7–9, 2009. Slides.
  
• Diameter of Polyhedra: Limits of Abstraction. F. Eisenbrand, N. Hähnle and T. Rothvoß. 25th Annual ACM Symposium on Computational Geometry (SoCG'09), Aarhus, Denmark, June 8-10, 2009
• Convexly independent subsets of the Minkowski sum of planar point sets. F. Eisenbrand, J. Pach, T. Rothvoß and N. B. Sopher. Electronic Journal of Combinatorics, Vol 15, 2008.
• Static-priority Real-time Scheduling: Response Time Computation is NP-hard. F. Eisenbrand and T. Rothvoß. Real-Time Systems Symposium (RTSS'08), Barcelona, Nov. 30-3 Dec., 2008.
• A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation. F. Eisenbrand and T. Rothvoß. Automata, Languages and Programming (ICALP'08), Reykjavik, Iceland, July 7-11, 2008. Slides.
  
• Approximating connected facility location problems via Random facility sampling and core detouring. F. Eisenbrand, F. Grandoni, T. Rothvoß and G. Schäfer. Proceeding of Nineteenth annual ACM-SIAM Symposium (SODA '08), San Francisco, California, 20-22.01.2008. Slides.
• On the computational complexity of periodic scheduling. T. Rothvoss, (directed by F. Eisenbrand). PhD thesis. EPFL, Lausanne, Switzerland. 2009. Slides.
• Algorithms for Virtual Private Networks. T. Rothvoß (directed by F. Eisenbrand). Master's thesis. TU Dortmund, Germany. 2006.