default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDThomas Rothvoß
Thomas Rothvoss
Person information
- affiliation: University of Washington, Seattle, Department of Mathematics
- affiliation: Massachusetts Institute of Technology, Mathematics Department
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[c42]Sally Dong, Thomas Rothvoss:
The Extension Complexity of Polytopes with Bounded Integral Slack Matrices. IPCO 2024: 113-123- [c41]Janardhan Kulkarni
, Victor Reis, Thomas Rothvoss:
Optimal Online Discrepancy Minimization. STOC 2024: 1832-1840 - 2023
- [j20]Victor Reis, Thomas Rothvoss:
Vector balancing in Lebesgue spaces. Random Struct. Algorithms 62(3): 667-688 (2023) - [c40]Victor Reis, Thomas Rothvoss:
The Subspace Flatness Conjecture and Faster Integer Programming. FOCS 2023: 974-988 - [c39]Rainie Bozzai, Victor Reis, Thomas Rothvoss:
The Vector Balancing Constant for Zonotopes. FOCS 2023: 1292-1300 - [c38]Daniel Dadush, Friedrich Eisenbrand, Thomas Rothvoss:
From Approximate to Exact Integer Programming. IPCO 2023: 100-114 - [i41]Victor Reis, Thomas Rothvoss:
The Subspace Flatness Conjecture and Faster Integer Programming. CoRR abs/2303.14605 (2023) - [i40]Sally Dong, Thomas Rothvoss:
Polytopes with Bounded Integral Slack Matrices Have Sub-Exponential Extension Complexity. CoRR abs/2307.16159 (2023) - [i39]Janardhan Kulkarni, Victor Reis, Thomas Rothvoss:
Optimal Online Discrepancy Minimization. CoRR abs/2308.01406 (2023) - [i38]Rainie Bozzai, Thomas Rothvoss:
Stronger Coreset Bounds for Kernel Density Estimators via Chaining. CoRR abs/2310.08548 (2023) - 2022
- [c37]Thomas Rothvoss, Moritz Venzin:
Approximate $\mathrm {CVP}_{}$ in Time 20.802 n - Now in Any Norm! IPCO 2022: 440-453 - [c36]Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Sai Sandeep, Jakub Tarnawski, Yihao Zhang:
On the Hardness of Scheduling With Non-Uniform Communication Delays. SODA 2022: 316-328 - [i37]Victor Reis, Thomas Rothvoss:
Approximate Carathéodory bounds via Discrepancy Theory. CoRR abs/2207.03614 (2022) - [i36]Laurel Heck, Victor Reis, Thomas Rothvoss:
The Vector Balancing Constant for Zonotopes. CoRR abs/2210.16460 (2022) - [i35]Daniel Dadush, Friedrich Eisenbrand, Thomas Rothvoss:
From approximate to exact integer programming. CoRR abs/2211.03859 (2022) - 2021
- [j19]Elaine Levey, Thomas Rothvoß:
A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies. SIAM J. Comput. 50(3) (2021) - [c35]Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Jakub Tarnawski, Yihao Zhang:
Scheduling with Communication Delays via LP Hierarchies and Clustering II: Weighted Completion Times on Related Machines. SODA 2021: 2958-2977 - [c34]Marcin Bienkowski, Martin Böhm, Martin Koutecký, Thomas Rothvoß, Jirí Sgall, Pavel Veselý:
Improved Analysis of Online Balanced Clustering. WAOA 2021: 224-233 - [i34]Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Sai Sandeep, Jakub Tarnawski, Yihao Zhang:
On the Hardness of Scheduling With Non-Uniform Communication Delays. CoRR abs/2105.00111 (2021) - [i33]Marcin Bienkowski, Martin Böhm, Martin Koutecký, Thomas Rothvoß, Jirí Sgall, Pavel Veselý:
Improved Analysis of Online Balanced Clustering. CoRR abs/2107.00145 (2021) - [i32]Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, Amir Yehudayoff:
Tight bounds on the Fourier growth of bounded functions on the hypercube. CoRR abs/2107.06309 (2021) - [i31]Thomas Rothvoss, Moritz Venzin:
Approximate CVP in time 20.802 n - now in any norm! CoRR abs/2110.02387 (2021) - [i30]Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, Amir Yehudayoff:
Tight bounds on the Fourier growth of bounded functions on the hypercube. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [j18]Michel X. Goemans, Thomas Rothvoss:
Polynomiality for Bin Packing with a Constant Number of Item Types. J. ACM 67(6): 38:1-38:21 (2020) - [c33]Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Jakub Tarnawski, Yihao Zhang:
Scheduling with Communication Delays via LP Hierarchies and Clustering. FOCS 2020: 822-833 - [c32]Victor Reis, Thomas Rothvoss:
Linear Size Sparsifier and the Geometry of the Operator Norm Ball. SODA 2020: 2337-2348 - [c31]Sami Davies, Thomas Rothvoss, Yihao Zhang:
A Tale of Santa Claus, Hypergraphs and Matroids. SODA 2020: 2748-2757 - [i29]Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Jakub Tarnawski, Yihao Zhang:
Scheduling with Communication Delays via LP Hierarchies and Clustering. CoRR abs/2004.09682 (2020) - [i28]Victor Reis, Thomas Rothvoss:
Vector Balancing in Lebesgue Spaces. CoRR abs/2007.05634 (2020)
2010 – 2019
- 2019
- [c30]Rebecca Hoberg, Thomas Rothvoss:
A Fourier-Analytic Approach for the Discrepancy of Random Set Systems. SODA 2019: 2547-2556 - [i27]Victor Reis, Thomas Rothvoss:
Linear Size Sparsifier and the Geometry of the Operator Norm Ball. CoRR abs/1907.02145 (2019) - 2018
- [i26]Rebecca Hoberg, Thomas Rothvoss:
A Fourier-Analytic Approach for the Discrepancy of Random Set Systems. CoRR abs/1806.04484 (2018) - [i25]Sami Davies, Thomas Rothvoss, Yihao Zhang:
A Tale of Santa Claus, Hypergraphs and Matroids. CoRR abs/1807.07189 (2018) - 2017
- [j17]Thomas Rothvoß, Laura Sanità:
0/1 Polytopes with Quadratic Chvátal Rank. Oper. Res. 65(1): 212-220 (2017) - [j16]Thomas Rothvoss:
The Matching Polytope has Exponential Extension Complexity. J. ACM 64(6): 41:1-41:19 (2017) - [j15]Thomas Rothvoss:
Constructive Discrepancy Minimization for Convex Sets. SIAM J. Comput. 46(1): 224-234 (2017) - [c29]Rebecca Hoberg, Harishchandra Ramadas, Thomas Rothvoss, Xin Yang:
Number Balancing is as Hard as Minkowski's Theorem and Shortest Vector. IPCO 2017: 254-266 - [c28]Rebecca Hoberg, Thomas Rothvoss:
An Improved Deterministic Rescaling for Linear Programming Algorithms. IPCO 2017: 267-278 - [c27]Avi Levy, Harishchandra Ramadas, Thomas Rothvoss:
Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method. IPCO 2017: 380-391 - [c26]Rebecca Hoberg, Thomas Rothvoss:
A Logarithmic Additive Integrality Gap for Bin Packing. SODA 2017: 2616-2625 - 2016
- [j14]Fabrizio Grandoni, Thomas Rothvoß:
Pricing on Paths: A PTAS for the Highway Problem. SIAM J. Comput. 45(2): 216-231 (2016) - [j13]Thomas Rothvoss:
Better Bin Packing Approximations via Discrepancy Theory. SIAM J. Comput. 45(3): 930-946 (2016) - [c25]Elaine Levey, Thomas Rothvoss:
A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies. STOC 2016: 168-177 - [i24]Thomas Rothvoss:
Lecture Notes on the ARV Algorithm for Sparsest Cut. CoRR abs/1607.00854 (2016) - [i23]Avi Levy, Harishchandra Ramadas, Thomas Rothvoss:
Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method. CoRR abs/1611.08752 (2016) - [i22]Rebecca Hoberg, Harishchandra Ramadas, Thomas Rothvoss, Xin Yang:
Number Balancing is as hard as Minkowski's Theorem and Shortest Vector. CoRR abs/1611.08757 (2016) - [i21]Rebecca Hoberg, Thomas Rothvoss:
An Improved Deterministic Rescaling for Linear Programming Algorithms. CoRR abs/1612.04782 (2016) - 2015
- [j12]Robert I. Davis, Alan Burns, Sanjoy K. Baruah, Thomas Rothvoß, Laurent George, Oliver Gettings:
Exact comparison of fixed priority and EDF scheduling based on speedup factors for both pre-emptive and non-pre-emptive paradigms. Real Time Syst. 51(5): 566-601 (2015) - [i20]Rebecca Hoberg, Thomas Rothvoss:
A Logarithmic Additive Integrality Gap for Bin Packing. CoRR abs/1503.08796 (2015) - [i19]Elaine Levey, Thomas Rothvoss:
A Lasserre-based $(1+\varepsilon)$-approximation for $Pm \mid p_j=1, \textrm{prec} \mid C_{\max}$. CoRR abs/1509.07808 (2015) - 2014
- [c24]Thomas Rothvoß:
Constructive Discrepancy Minimization for Convex Sets. FOCS 2014: 140-145 - [c23]Michel X. Goemans, Thomas Rothvoß:
Polynomiality for Bin Packing with a Constant Number of Item Types. SODA 2014: 830-839 - [c22]Thomas Rothvoß:
The matching polytope has exponential extension complexity. STOC 2014: 263-272 - [i18]Thomas Rothvoß:
Constructive discrepancy minimization for convex sets. CoRR abs/1404.0339 (2014) - [i17]Thomas Rothvoß:
A direct proof for Lovett's bound on the communication complexity of low rank matrices. CoRR abs/1409.6366 (2014) - 2013
- [j11]Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, Laura Sanità:
Steiner Tree Approximation via Iterative Randomized Rounding. J. ACM 60(1): 6:1-6:33 (2013) - [j10]Thomas Rothvoß:
Some 0/1 polytopes need exponential size extended formulations. Math. Program. 142(1-2): 255-268 (2013) - [j9]Béla Bollobás, David Pritchard, Thomas Rothvoß, Alex D. Scott:
Cover-Decomposition and Polychromatic Numbers. SIAM J. Discret. Math. 27(1): 240-256 (2013) - [j8]Friedrich Eisenbrand, Dömötör Pálvölgyi, Thomas Rothvoß:
Bin Packing via Discrepancy of Permutations. ACM Trans. Algorithms 9(3): 24:1-24:15 (2013) - [c21]Thomas Rothvoß:
Approximating Bin Packing within O(log OPT * Log Log OPT) Bins. FOCS 2013: 20-29 - [c20]Thomas Rothvoß:
A Simpler Proof for $O(\textrm{Congestion} + \textrm{Dilation})$ Packet Routing. IPCO 2013: 336-348 - [c19]Thomas Rothvoß, Laura Sanità:
0/1 Polytopes with Quadratic Chvátal Rank. IPCO 2013: 349-361 - [i16]Thomas Rothvoß:
Approximating Bin Packing within O(log OPT * log log OPT) bins. CoRR abs/1301.4010 (2013) - [i15]Michel X. Goemans, Thomas Rothvoß:
Polynomiality for Bin Packing with a Constant Number of Item Types. CoRR abs/1307.5108 (2013) - [i14]Thomas Rothvoß:
The matching polytope has exponential extension complexity. CoRR abs/1311.2369 (2013) - 2012
- [j7]Samuel Fiorini, Thomas Rothvoß, Hans Raj Tiwary:
Extended Formulations for Polygons. Discret. Comput. Geom. 48(3): 658-668 (2012) - [c18]Thomas Rothvoß:
The entropy rounding method in approximation algorithms. SODA 2012: 356-372 - [c17]Michel X. Goemans, Neil Olver, Thomas Rothvoß, Rico Zenklusen:
Matroids and integrality gaps for hypergraphic steiner tree relaxations. STOC 2012: 1161-1176 - [i13]Thomas Rothvoß, Laura Sanità:
0/1 Polytopes with Quadratic Chvatal Rank. CoRR abs/1204.4753 (2012) - [i12]Thomas Rothvoß:
A simpler proof for O(congestion + dilation) packet routing. CoRR abs/1206.3718 (2012) - 2011
- [j6]Fabrizio Grandoni, Thomas Rothvoß, Laura Sanità:
From Uncertainty to Nonlinearity: Solving Virtual Private Network via Single-Sink Buy-at-Bulk. Math. Oper. Res. 36(2): 185-204 (2011) - [c16]Béla Bollobás, David Pritchard, Thomas Rothvoß, Alex D. Scott:
Cover-Decomposition and Polychromatic Numbers. ESA 2011: 799-810 - [c15]Friedrich Eisenbrand, Naonori Kakimura, Thomas Rothvoß, Laura Sanità:
Set Covering with Ordered Replacement: Additive and Multiplicative Gaps. IPCO 2011: 170-182 - [c14]Fabrizio Grandoni, Thomas Rothvoß:
Approximation Algorithms for Single and Multi-Commodity Connected Facility Location. IPCO 2011: 248-260 - [c13]Friedrich Eisenbrand, Dömötör Pálvölgyi, Thomas Rothvoß:
Bin Packing via Discrepancy of Permutations. SODA 2011: 476-481 - [c12]Fabrizio Grandoni, Thomas Rothvoß:
Pricing on Paths: A PTAS for the Highway Problem. SODA 2011: 675-684 - [i11]Thomas Rothvoß:
The Entropy Rounding Method in Approximation Algorithms. CoRR abs/1104.4597 (2011) - [i10]Thomas Rothvoß:
Some 0/1 polytopes need exponential size extended formulations. CoRR abs/1105.0036 (2011) - [i9]Samuel Fiorini, Thomas Rothvoß, Hans Raj Tiwary:
Extended formulations for polygons. CoRR abs/1107.0371 (2011) - [i8]Thomas Rothvoß:
Directed Steiner Tree and the Lasserre Hierarchy. CoRR abs/1111.5473 (2011) - [i7]Michel X. Goemans, Neil Olver, Thomas Rothvoß, Rico Zenklusen:
Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations. CoRR abs/1111.7280 (2011) - 2010
- [j5]Roberto Cominetti, José R. Correa, Thomas Rothvoß, Jaime San Martín:
Optimal Selection of Customers for a Last-Minute Offer. Oper. Res. 58(4-Part-1): 878-888 (2010) - [j4]Friedrich Eisenbrand, Fabrizio Grandoni, Thomas Rothvoß, Guido Schäfer:
Connected facility location via random facility sampling and core detouring. J. Comput. Syst. Sci. 76(8): 709-726 (2010) - [j3]Friedrich Eisenbrand, Nicolai Hähnle, Alexander A. Razborov, Thomas Rothvoß:
Diameter of Polyhedra: Limits of Abstraction. Math. Oper. Res. 35(4): 786-794 (2010) - [c11]Fabrizio Grandoni, Thomas Rothvoß:
Network Design via Core Detouring for Problems without a Core. ICALP (1) 2010: 490-502 - [c10]Friedrich Eisenbrand, Thomas Rothvoß:
EDF-schedulability of Synchronous Periodic Task Systems is coNP-hard. SODA 2010: 1029-1034 - [c9]Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, Laura Sanità:
An improved LP-based approximation for steiner tree. STOC 2010: 583-592 - [c8]Andreas Karrenbauer, Thomas Rothvoß:
A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks. WAOA 2010: 166-177 - [i6]Friedrich Eisenbrand, Nicolai Hähnle, Alexander A. Razborov, Thomas Rothvoß:
Diameter of Polyhedra: Limits of Abstraction. Flexible Network Design 2010 - [i5]Friedrich Eisenbrand, Thomas Rothvoß:
Recent Hardness Results for Periodic Uni-processor Scheduling. Scheduling 2010 - [i4]Fabrizio Grandoni, Thomas Rothvoß:
Prizing on Paths: A PTAS for the Highway Problem. CoRR abs/1004.3051 (2010) - [i3]Friedrich Eisenbrand, Dömötör Pálvölgyi, Thomas Rothvoß:
Bin Packing via Discrepancy of Permutations. CoRR abs/1007.2170 (2010) - [i2]David Pritchard, Thomas Rothvoß:
Edge-Colouring Hypergraphs Properly (Covering with Matchings) or Polychromatically (Packing Covers). CoRR abs/1009.6144 (2010) - [i1]Friedrich Eisenbrand, Naonori Kakimura, Thomas Rothvoß, Laura Sanità:
Set Covering with Ordered Replacement -- Additive and Multiplicative Gaps. CoRR abs/1012.3295 (2010)
2000 – 2009
- 2009
- [j2]Robert I. Davis, Thomas Rothvoß, Sanjoy K. Baruah, Alan Burns:
Exact quantification of the sub-optimality of uniprocessor fixed priority pre-emptive scheduling. Real Time Syst. 43(3): 211-258 (2009) - [c7]Friedrich Eisenbrand, Thomas Rothvoß:
New Hardness Results for Diophantine Approximation. APPROX-RANDOM 2009: 98-110 - [c6]Thomas Rothvoß, Laura Sanità:
On the Complexity of the Asymmetric VPN Problem. APPROX-RANDOM 2009: 326-338 - [c5]Friedrich Eisenbrand, Nicolai Hähnle, Thomas Rothvoß:
Diameter of polyhedra: limits of abstraction. SCG 2009: 386-392 - [c4]Andreas Karrenbauer, Thomas Rothvoß:
An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-Time Scheduling. ESA 2009: 432-443 - 2008
- [j1]Friedrich Eisenbrand, János Pach, Thomas Rothvoß, Nir B. Sopher:
Convexly Independent Subsets of the Minkowski Sum of Planar Point Sets. Electron. J. Comb. 15(1) (2008) - [c3]Friedrich Eisenbrand, Thomas Rothvoß:
A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation. ICALP (1) 2008: 246-257 - [c2]Friedrich Eisenbrand, Thomas Rothvoß:
Static-Priority Real-Time Scheduling: Response Time Computation Is NP-Hard. RTSS 2008: 397-406 - [c1]Friedrich Eisenbrand, Fabrizio Grandoni, Thomas Rothvoß, Guido Schäfer:
Approximating connected facility location problems via random facility sampling and core detouring. SODA 2008: 1174-1183
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-07-05 21:07 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
