Thomas Rothvoss

from Wikipedia, the free encyclopedia

Thomas Rothvoss , also Rothvoss, (* around 1984) is a German computer scientist and mathematician.

Rothvoss studied computer science at the TU Dortmund from 2002 to 2006 (diploma from Friedrich Eisenbrand : Algorithms for virtual private networks ), continued his studies in Paderborn and at the EPFL in Lausanne , where he received his doctorate from Eisenbrand in 2009 ( On the computational complexity of periodic scheduling ). From 2011 he was a post-doctoral student with Michel X. Goemans at the Massachusetts Institute of Technology (as a Fedor Lynen scholarship holder), where he became an instructor in 2013. In 2014 he became an assistant professor at the University of Washington in Seattle, in both the math and computer science faculties.

He deals with linear and integer programming, combinatorics ( e.g. scheduling ), theoretical computer science (complexity theory), network design, approximation algorithms ( e.g. the Steiner tree problem ) and discrete optimization. In 2014 he solved a difficult problem about the extension complexity of the convex hull of all matchings of a graph with n nodes. He showed that this is not polynomial in n, but exponential.

In 2018 he received the Fulkerson Prize .

He was a Packard Fellow (2016) and a Sloan Research Fellow.

Fonts (selection)

  • with Eisenbrand, Grandoni, Guido Schäfer: Approximating connected facility location problems via random facility sampling and core detouring, SODA 2008
  • with F. Eisenbrand: Static-priority real-time scheduling: Response time computation is NP-hard, Real-Time Systems Symposium, 2008, pp. 397-406
  • with F. Eisenbrand: EDF-schedulability of synchronous periodic task systems is coNP-hard, SODA 2010, pp. 1029-1034
  • with J. Byrka, F. Grandoni, L. Sanità: An Improved LP-based Approximation for Steiner Tree, STOC 2010, pp. 583–592 (STOC 2010 Best Paper Award)
  • with S. Fiorini, H. Tiwary: Extended formulations for polygons, Discrete & Computational Geometry, Volume 48, No. 3, 2012, pp. 658–668, Arxiv
  • with Goemans, Olver, Zenklusen: Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations, STOC 2012, pp. 1161–1176
  • with J. Byrka, F. Grandoni, L. Sanità: Steiner tree approximation via iterative randomized rounding, Journal of the ACM (JACM), Volume 60, Issue 1, 2013, p. 6
  • The matching polytope has exponential extension complexity, ACM Symposium on the Theory of Computing (STOC) 2014 (STOC 2014 Best Paper Prize), Arxiv , also published in J. Journal of the ACM (JACM), Volume 64, 2017, Issue 6, P. 41
  • mit Goemans: Polynomiality for Bin Packing with a Constant Number of Item Types, Symposium on Discrete Algorithms (SODA) 2014, (SODA Best Paper Award 2014), Arxiv
  • Constructive discrepancy minimization for convex sets, Foundations of Computer Science (FOCS) 2014, Arxiv
  • with Rebecca Hoberg: An Improved Deterministic Rescaling for Linear Programming Algorithms, IPCO 2017, Arxiv 2016

Web links

References and comments

  1. ↑ The extension of a polytope P is a polytope Q together with affine or projective mappings from Q to P and the complexity of the extension is the minimum number of sides of Q
personal data
SURNAME Rothvoss, Thomas
ALTERNATIVE NAMES Rothvoss, Thomas
BRIEF DESCRIPTION German computer scientist
DATE OF BIRTH around 1984