Skip to main content
This page contains documents that have been archived before
April 24, 2026. The page and its content are not in active use
and are not updated anymore.
Lecture notes and expositions
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.