People‎ > ‎Dirk Oliver Theis‎ > ‎

CV of Dirk Oliver Theis

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


This page is no longer maintained, see new homepage of Dirk Oliver Theis.


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 


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