Thomas Rothvoß

Orcid: 0009-0007-8314-0963

Affiliations:
  • University of Washington, Seattle, Department of Mathematics
  • Massachusetts Institute of Technology, Mathematics Department


According to our database1, Thomas Rothvoß authored at least 68 papers between 2008 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Optimal Online Discrepancy Minimization.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

The Extension Complexity of Polytopes with Bounded Integral Slack Matrices.
Proceedings of the Integer Programming and Combinatorial Optimization, 2024

2023
Vector balancing in Lebesgue spaces.
Random Struct. Algorithms, May, 2023

Stronger Coreset Bounds for Kernel Density Estimators via Chaining.
CoRR, 2023

Polytopes with Bounded Integral Slack Matrices Have Sub-Exponential Extension Complexity.
CoRR, 2023

From Approximate to Exact Integer Programming.
Proceedings of the Integer Programming and Combinatorial Optimization, 2023

The Subspace Flatness Conjecture and Faster Integer Programming.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

The Vector Balancing Constant for Zonotopes.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022
The Vector Balancing Constant for Zonotopes.
CoRR, 2022

Approximate Carathéodory bounds via Discrepancy Theory.
CoRR, 2022

On the Hardness of Scheduling With Non-Uniform Communication Delays.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Approximate $\mathrm {CVP}_{}$ in Time 2<sup>0.802 n</sup> - Now in Any Norm!
Proceedings of the Integer Programming and Combinatorial Optimization, 2022

2021
A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies.
SIAM J. Comput., 2021

Tight bounds on the Fourier growth of bounded functions on the hypercube.
Electron. Colloquium Comput. Complex., 2021

Approximate CVP in time 2<sup>0.802 n</sup> - now in any norm!
CoRR, 2021

Improved Analysis of Online Balanced Clustering.
Proceedings of the Approximation and Online Algorithms - 19th International Workshop, 2021

Scheduling with Communication Delays via LP Hierarchies and Clustering II: Weighted Completion Times on Related Machines.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020
Polynomiality for Bin Packing with a Constant Number of Item Types.
J. ACM, 2020

Linear Size Sparsifier and the Geometry of the Operator Norm Ball.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

A Tale of Santa Claus, Hypergraphs and Matroids.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Scheduling with Communication Delays via LP Hierarchies and Clustering.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019
A Fourier-Analytic Approach for the Discrepancy of Random Set Systems.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2017
Constructive Discrepancy Minimization for Convex Sets.
SIAM J. Comput., 2017

The Matching Polytope has Exponential Extension Complexity.
J. ACM, 2017

0/1 Polytopes with Quadratic Chvátal Rank.
Oper. Res., 2017

A Logarithmic Additive Integrality Gap for Bin Packing.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method.
Proceedings of the Integer Programming and Combinatorial Optimization, 2017

Number Balancing is as Hard as Minkowski's Theorem and Shortest Vector.
Proceedings of the Integer Programming and Combinatorial Optimization, 2017

An Improved Deterministic Rescaling for Linear Programming Algorithms.
Proceedings of the Integer Programming and Combinatorial Optimization, 2017

2016
Better Bin Packing Approximations via Discrepancy Theory.
SIAM J. Comput., 2016

Pricing on Paths: A PTAS for the Highway Problem.
SIAM J. Comput., 2016

Lecture Notes on the ARV Algorithm for Sparsest Cut.
CoRR, 2016

2015
Exact comparison of fixed priority and EDF scheduling based on speedup factors for both pre-emptive and non-pre-emptive paradigms.
Real Time Syst., 2015

A Lasserre-based $(1+\varepsilon)$-approximation for $Pm \mid p_j=1, \textrm{prec} \mid C_{\max}$.
CoRR, 2015

2014
A direct proof for Lovett's bound on the communication complexity of low rank matrices.
CoRR, 2014

2013
Bin Packing via Discrepancy of Permutations.
ACM Trans. Algorithms, 2013

Cover-Decomposition and Polychromatic Numbers.
SIAM J. Discret. Math., 2013

Some 0/1 polytopes need exponential size extended formulations.
Math. Program., 2013

Steiner Tree Approximation via Iterative Randomized Rounding.
J. ACM, 2013

A Simpler Proof for $O(\textrm{Congestion} + \textrm{Dilation})$ Packet Routing.
Proceedings of the Integer Programming and Combinatorial Optimization, 2013

Approximating Bin Packing within O(log OPT * Log Log OPT) Bins.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012
Extended Formulations for Polygons.
Discret. Comput. Geom., 2012

A simpler proof for O(congestion + dilation) packet routing
CoRR, 2012

Matroids and integrality gaps for hypergraphic steiner tree relaxations.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

The entropy rounding method in approximation algorithms.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011
From Uncertainty to Nonlinearity: Solving Virtual Private Network via Single-Sink Buy-at-Bulk.
Math. Oper. Res., 2011

Directed Steiner Tree and the Lasserre Hierarchy
CoRR, 2011

Approximation Algorithms for Single and Multi-Commodity Connected Facility Location.
Proceedings of the Integer Programming and Combinatoral Optimization, 2011

Set Covering with Ordered Replacement: Additive and Multiplicative Gaps.
Proceedings of the Integer Programming and Combinatoral Optimization, 2011

2010
Diameter of Polyhedra: Limits of Abstraction.
Math. Oper. Res., 2010

Connected facility location via random facility sampling and core detouring.
J. Comput. Syst. Sci., 2010

Optimal Selection of Customers for a Last-Minute Offer.
Oper. Res., 2010

Edge-Colouring Hypergraphs Properly (Covering with Matchings) or Polychromatically (Packing Covers)
CoRR, 2010

Prizing on Paths: A PTAS for the Highway Problem
CoRR, 2010

A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks.
Proceedings of the Approximation and Online Algorithms - 8th International Workshop, 2010

An improved LP-based approximation for steiner tree.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

EDF-schedulability of Synchronous Periodic Task Systems is coNP-hard.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Network Design via Core Detouring for Problems without a Core.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Recent Hardness Results for Periodic Uni-processor Scheduling.
Proceedings of the Scheduling, 14.02. - 19.02.2010, 2010

2009
Exact quantification of the sub-optimality of uniprocessor fixed priority pre-emptive scheduling.
Real Time Syst., 2009

An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-Time Scheduling.
Proceedings of the Algorithms, 2009

Diameter of polyhedra: limits of abstraction.
Proceedings of the 25th ACM Symposium on Computational Geometry, 2009

On the Complexity of the Asymmetric VPN Problem.
Proceedings of the Approximation, 2009

New Hardness Results for Diophantine Approximation.
Proceedings of the Approximation, 2009

2008
Convexly Independent Subsets of the Minkowski Sum of Planar Point Sets.
Electron. J. Comb., 2008

Approximating connected facility location problems via random facility sampling and core detouring.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Static-Priority Real-Time Scheduling: Response Time Computation Is NP-Hard.
Proceedings of the 29th IEEE Real-Time Systems Symposium, 2008

A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008


  Loading...