People‎ > ‎Dirk Oliver Theis‎ > ‎

CV of Dirk Oliver Theis

Résumé -- Research -- Publications -- Teaching -- Funding -- Talks -- Hobby


Still Outdated! (Check back soon.)

Résumé

9/2017 -- now Assoc. Professor
University of Tartu, Estonia
2/2013 -- 08/2017 Senior Lecturer (temporary position) in Theoretical Computer Science
University of Tartu, Estonia
5/2012 Habilitation* in Mathematics
6-8/2011 Visiting Professor
Brock University, St.Catharines, ON
5/2009 -- 2/2013 PostDoc / Priv.-Doz.*
Otto von Guericke University Magdeburg, Germany
3/2007 -- 4/2009 PostDoc
Université Libre de Bruxelles (ULB), Brussels, Belgium
1/2006 -- 2/2007 PostDoc in Heidelberg
12/2005 PhD in Mathematics/Computer Science (summa cum laude)
Ruprecht Karls University of Heidelberg, Germany
8/2002           Diplom in Mathematics w/ minor Computer Science
Ruprecht Karls University of Heidelberg, Germany
top

Research

My research is in Algorithms, Randomness, and Combinatorics, as well as Optimization with applications. 
Here are some slides of recent talks I've given about my research.
top

List of Publications


My recent preprints are on the arXiv (with a few exceptions): http://arxiv.org/a/theis_d_1

In preparation


Submitted

Accepted

  • Fooling-sets and rank.
    With M. Friesen (Magdeburg), A. Hamed, and T. Lee (Singapore).
    Eur. J. Comb. (arXiv:1208.2920)

Published

  • On the facial structure of Symmetric and Graphical Traveling Salesman Polyhedra.
    Discrete Opt. 12 (2014) 10--25 (arXiv:0712.1269)
  • An algorithm for random signed 3-SAT with intervals.
    With K. Ballerstein (ETH Zurich).
    Theor. Comput. Sci. 524 (2014) 1--26 (Blog post, arXiv:1105.2525)
  • A note on the Cops & Robber game on graphs embedded in non-orientable surfaces.
    With N. Clarke (Acadia University, NS), S. Fiorini (Brussels), G. Joret (Brussels).
    Graphs Comb. 30:1 (2014) 119--124 (Journal link, arXiv:0803.0538)
  • Compact formulations of the Steiner TSP and related problems.
    With A.N. Letchford and S.D. Nasiri (Lancaster, UK).
    Europ. J. Oper. Res. 228:1 (2013) 83--93 (arXiv:1203.3854)
  • Combinatorial bounds on nonnegative rank and extended formulations.
    With S. Fiorini (ULB, Brussels), V. Kaibel and K. Pashkovich (Magdeburg).
    Discrete Math. 313:1 (2013) 67--83 (arXiv:1111.0444)
  • Symmetry matters for sizes of extended formulations.
    With K. Pashkovich & V. Kaibel (Magdeburg).
    SIAM J. Discrete Math. 26:3 (2012) 1361--1382 (arXiv:0911.3712)
  • Small minors in dense graphs.
    With S. Florin, G. Joret (Brussels), and D. Wood (Melbourne).
    Eur. J. Comb. 33 (2012), 1226--1245 (arXiv:1005.0895)
  • Random lifts of K5\e are 3-colourable.
    With B. Farzad (Brock University, ON).
    SIAM J. Discrete Math. 26:1 (2012), 169--179 (Blog post 1, Blog post 2, arXiv:1003.1527)
  • A Branch-and-Cut solver for the Maximum Stable Set problem.
    With S. Rebennack (Boulder, CO), M. Oswald, G. Reinelt and H. Seitz (Heidelberg).
    J. Comb. Opt. 21:4 (2011), 434--457
  • The Cops & Robber game on graphs with forbidden (induced) subgraphs.
    With G. Joret and M. Kaminski (Brussels).
    Contrib. Discrete Math. 5:2 (2010), 40--51. (arXiv:0804.4145)
  • The Virtual Private Network Design Problem with Concave Costs.
    With S. Fiorini (Brussels), G. Oriolo and L. Sanità (Rome).
    SIAM J. Discrete Math. 24 (2010), 1080--1090. (arXiv:0812.2355)
  • On a Class of Metrics Related to Graph Layout Problems.
    With H. Seitz, A.N. Letchford, G. Reinelt.
    Linear Algebra Appl. 433 (2010), 1760--1777. (arXiv:0909.0910)
  • A note on the relationship between the Graphical Traveling Salesman Polyhedron, the Symmetric Traveling Salesman Polytope, and the Metric Cone.
    Discrete Appl. Math. 158:10 (2010), 1118--1120. (arXiv:0801.1652)
  • Odd minimum cut sets and b-matchings revisited.
    With A.N. Letchford and G. Reinelt.
    SIAM J. Discrete Math. 22:4 (2008), 1480--1487.
  • On the General Routing polytope.
    With G. Reinelt.
    Discrete Appl. Math. 156:3 (2008), 368--384.
  • Computing finest mincut partitions of a graph and application to routing problems.
    With K.M. Wenger and G. Reinelt
    Discrete Appl. Math. 156:3 (2008), 385--396.
  • On the graphical relaxation of the symmetric traveling salesman polytope.
    With M. Oswald and G. Reinelt.
    Math. Program. Ser. B 110 (2007), 175--193.
  • A note on the Undirected Rural Postman Problem polytope.
    With G. Reinelt
    Math. Program. Ser. A 106:3 (2006), 447--452.
  • Transformation of facets of the General Routing Problem polytope.
    With G. Reinelt.
    SIAM J. Optim. 16:1 (2005), 220--234.

In Conference Proceedings (top tier refereed conferences)

  • Fooling-sets and rank in nonzero characteristic (extended abstract).
    With M. Friesen (Magdeburg)
    Proceedings of EuroComb (2013) 383--390 (arXiv:1305.2468)
  • Symmetry matters for sizes of extended formulations.
    With K. Pashkovich & V. Kaibel (Magdeburg)
    IPCO XIV. F. Eisenbrand, F. B. Shepherd (Eds.) Integer Programming and Combinatorial Optimization 14 (2010).
  • Not every GTSP facet induces an STSP facet.
    With M. Oswald (Heidelberg) and G. Reinelt.
    IPCO XI. Jünger & Kaibel (Eds.) Integer Programming and Combinatorial Optimization 11 (2005)
  • A faster exact separation algorithm for blossom inequalities.
    With A.N. Letchford (Lancaster) and G. Reinelt.
    IPCO X. Nemhauser & Bienstock (Eds.) Integer Programming and Combinatorial Optimization 10 (2004)

Other Proceedings

  • The chromatic number of random lifts of K5\e.
    With B. Farzad (Brock University, CA).
    LAGOS'09 --- V Latin-American Algorithms, Graphs and Optimization Symposium
    Electron. Notes Discrete Math. 35 (2009), 311--316
  • The Virtual Private Network Design Problem with Concave Costs.
    With S. Fiorini (Brussels), G. Oriolo (Rome) and L. Sanità (Lausanne).
    In Oberwolfach Report No. 51/2008 (Workshop at the Mathematisches Forschungsinstitut Oberwolfach)

Miscellaneous

  • Dagstuhl Report 15082: ...
  • Dagstuhl Report 13082: Communication Complexity, Combinatorial Optimization, and lower bounds on the nonnegative rank of matrices.
    With T. Lee (NUS, Singapore), H. Klauck (Nanyang, Singapore), and L. Beasley (Utah State).
    arXiv:1305.4147 (2013)

Technical Reports

  • Support based lower bounds for the positive semidefinite rank of nonnegative matrices.
    With Troy Lee (CQT, Singapore).
    arXiv:1203.3961 (2012)
  • On some lower bounds on the number of bicliques needed to cover a bipartite graph
    arXiv:0708.1174 (2011)
  • The Virtual Private Network Design Tree Routing Conjecture for Outerplanar Networks.
    With S. Fiorini (Brussels), G. Oriolo and L. Sanità (Rome, Italy).
    arXiv:0711.2623 (2007)
  • The Cops & Robber game on series-parallel graphs.
    arXiv:0712.2908 (2007)

Theses

top

Teaching

Courses

University of Tartu
Fall 2014/5:
  • Discrete Mathematics (Compulsory for 1st year CS grad, 6 ECTS)
  • Extremal Combinatorics (PhD students, 6 ECTS)
Spring 2014:
  • Randomness in Computer Science (CS grad, 6 ECTS)
  • Problem Solving: Hypergraph theory (Math/CS grad, 6 ECTS)
Fall 2013/4:
  • Discrete Mathematics (Compulsory for 1st year CS grad, 6 ECTS)
  • Enumerative combinatorics (PhD students, 6 ECTS)
Spring 2013:
  • Topics in Mathematics for Cryptology
Brock U, St Catharines, ON
  • Mathematics for Computer Scientists
Otto-von-Guericke University of Magdeburg
  • Algorithms with random input and statistical mechanics
  • Probabilistic Methods in Combinatorics
Heidelberg University
  • Fourier-analytic Methods in Combinatorics
  • Combinatorics

Undergraduate Research

  • Research-oriented Bachelor theses
  • Research projects with Master students
  • Master's theses

Students

Current students:
Past students: (Names in red indicate that the project lead to the publication of a research paper in a journal or conference.)
  • Kaveh Khoshkhah (visiting PhD student, BSc Sharif)
  • Artur Bauer (Diploma, Magdeburg, Known and new facts about 3-1-improper colorings of planar graphs)
  • Sebastian Schindler (Bachelor thesis, Magdeburg, Extended formulations and biclique covering) 
  • Mirjam Friesen (Bachelor thesis, Magdeburg, Extended formulations and biclique covering) 
  • Christian Laus (Research project, Magdeburg, Satisfiability of random regular signed formulas) 
  • Michel Bode (Diploma, Magdeburg, Good edge-labelings of graphs) 
  • Gordon Schulze (Diploma, Magdeburg, Algorithmic questions in Cops & Robber games on graphs) 
  • Maximilian Geier (Diploma, Heidelberg, Cops & Robber on finite metric spaces and subdivisions of graphs) 
  • David Jesgarz (Diploma, Heidelberg, Picking tour optimization for Bosch GmbH)
  • Tatjana Jesgarz (Diploma, Heidelberg, Hochschild & simplicial cohomology of posets) 
  • Thorsten Bonato (Diploma, Heidelberg, Polyhedral subdivisions by projecting TSP polyhedra)
top

Funding

Contributions to successful proposals:
  • Dagstuhl Seminar Limitations of convex programming: lower bounds on extended formulations and factorization ranks (Dagstuhl web page), scheduled for Feb 2015
  • Dagstuhl Seminar Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices (Dagstuhl web page), Feb 2013
  • NSERC International Collaborative Funding Initiative grant (with B. Farzad, Brock U, ON)
  • 2-year Research Project funded by Deutsche Forschungsgemeinschaft (DFG) at University of Heidelberg. Topic: Polyhedral theory and algorithms for the Graphical Traveling Salesman Problem
top

Talks

Talks I gave on invitation or at invitation-only conferences, or at conferences with a competitive selection process.  (Contributed talks at open-participation conferences w/o competitive selection are not listed.)

I have given up writing these down.
  • Sep 2013: EuroComb'13.  Fooling sets and rank in non-zero characteristic. (slides)
  • July 2013: International Conference on Continuous Optimization, Lisbon, Portugal. Invited talk in the session organized by J. Gouveia and R. Thomas. Support-based lower bounds for the positive semidefinite rank of a nonnegative matrix. (slides)
  • July 2013: European Conference on Operational Research, Rome, Italy. Invited talk in the session organized by N.E. Clarke and B. Yang. The Cops & Robber game on graphs embedded in surfaces.
  • May 2013: Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Enschede, NL.  Fooling sets and rank in non-zero characteristic.
  • Aug 2012: International Symposium on Mathematical Programming, Berlin, Germany. Invited talk in the session organized by S. Fiorini.  Lower Bounds on Positive Semidefinite Rank and Positive Semidefinite Formulations of Combinatorial Optimization Problems.
  • Mar 2012: Centre for Quantum Technologies, Singapore.  Invited colloquium talk Combinatorial Optimization and Communication Complexity.
  • Jan 2011: Catholique Université de Louvain la Neuve, Louvain l.N., Belgium, Center for Operations Research and Econometrics (C.O.R.E.). Invited colloquium talk Projections of Polytopes, Nonnegative Rank of Matrices, and Nondeterministic Communication Complexity.
  • Sep 2010: Cargese Workshop on Combinatorial Optimization (topic: Extended Formulations) Combinatorial lower bounds to sizes of extended formulations.
  • Jan 2010: Aussois Workshop on Combinatorial Optimization.
  • April 2009: Brock University, St Catharines, CA, Department of Mathematics & Statistics. Invited colloquium talk The Cops & Robber game.
  • Nov 2008: Oberwolfach meeting on Combinatorial Optimization, Oberwolfach, Germany. Invited talk Virtual Private Network Design with concave costs.
  • Mai 2008: Dalhousie University, Halifax, CA, Department of Mathematics & Statistics. Invited colloquium talk The Cops & Robber game and forbidden (induced) subgraphs.
  • Sep 2007: Universitá degli studi di Roma Tor Vergata, Rome, Italy. Invited colloquium talk Subdividing the polar of a face.
  • April 2007: Ghent University, Ghent, Belgium, Department of Pure Mathematics and Computer Algebra. Invited colloquium talk On convex sets associated with certain metrics and permutations.
  • Dec 2006: Université Libre de Bruxelles, Brussels, Belgium. Invited colloquium talk On the Graphical Relaxation of the Symmetric Traveling Salesman Problem.
  • Aug 2006: International Symposium on Mathematical Programming, Rio de Janeiro, Brazil. Invited talk in the session organized by A. Lodi Results on the Graphical Relaxation of the Symmetric TSP.
  • Jan 2006: Aussois Workshop on Combinatorial Optimization
  • Oct 2005: University of Bayreuth, Bayreuth, Germany, Department of Mathematics. Invited colloquium talk On the Graphical Relaxation of the Symmetric TSP.
  • Mar 2005: Aussois Workshop on Combinatorial Optimization. Talk Not every GTSP-Facet defines an STSP-Facet.
  • Oct 2004: University of Valencia, Valencia, Spain. Invited talks Separation of some constraints for routing problems A survey of the cutting-plane approach to the Undirected General Routing Problem.
  • Jan 2004: Aussois Workshop on Combinatorial Optimization. Talk A faster exact separation algorithm for blossom inequalities.
  • Feb 2003: Conference on Routing and Location, Puerto de la Cruz, Spain. Invited talk The Undirected General Routing Problem
  • Mar 2003: Aussois Workshop on Combinatorial Optimization.
top

Hobby

I'm working on making the list longer. :)
When What Time Pace
June'14 Stadtlauf München Half Marathon 1:38:18 7:30
May'14 Gutenberg 2/3-Marathon Mainz 2:16:06 7:48
June'13 LBS Stuttgart Half Marathon 1:39:08 7:34
April'13 Vienna City Half Marathon (finished)
May'12 Salzburg Half Marathon (finished)
top