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 in Autumn 2023)
• 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 in Winter 2026)
• Design and Analysis of Algorithms (lecture notes for CSE 521 held in Autumn 2024)
• Computational Complexity (lecture notes for CSE 531 held in Winter 2024)

Publications (chronologically):

• The Subspace Flatness Conjecture. Proceedings article for the 2026 ICM in Pittsburgh, USA.
• 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 Bounds for 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 pseudo-polynomial 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 covered 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 disproved 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 uni-processor fixed-priority preemptive 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.