Résumé  Research  Publications  Teaching  Funding  Talks  Hobby
Still Outdated! (Check back soon.)
Résumé
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 (w ith a few exceptions): http://arxiv.org/a/theis_d_1
In preparation
Submitted
Accepted
 Foolingsets 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) 1025 (arXiv:0712.1269)
 An algorithm for random signed 3SAT with intervals.
With K. Ballerstein (ETH Zurich).
Theor. Comput. Sci. 524 (2014) 126 (Blog post, arXiv:1105.2525)
 A note on the Cops & Robber game on graphs embedded in nonorientable surfaces.
With N. Clarke (Acadia University, NS), S. Fiorini (Brussels), G. Joret (Brussels).
Graphs Comb. 30:1 (2014) 119124 (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) 8393 (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) 6783 (arXiv:1111.0444)
 Symmetry matters for sizes of extended formulations.
With K. Pashkovich & V. Kaibel (Magdeburg).
SIAM J. Discrete Math. 26:3 (2012) 13611382 (arXiv:0911.3712)
 Small minors in dense graphs.
With S. Florin, G. Joret (Brussels), and D. Wood (Melbourne).
Eur. J. Comb. 33 (2012), 12261245 (arXiv:1005.0895)
 Random lifts of K5\e are 3colourable.
With B. Farzad (Brock University, ON).
SIAM J. Discrete Math. 26:1 (2012), 169179 (Blog post 1, Blog post 2, arXiv:1003.1527)
 A BranchandCut 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), 434457
 The Cops & Robber game on graphs with forbidden (induced) subgraphs.
With G. Joret and M. Kaminski (Brussels).
Contrib. Discrete Math. 5:2 (2010), 4051. (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), 10801090. (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), 17601777. (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), 11181120. (arXiv:0801.1652)
 Odd minimum cut sets and bmatchings revisited.
With A.N. Letchford and G. Reinelt.
SIAM J. Discrete Math. 22:4 (2008), 14801487.
 On the General Routing polytope.
With G. Reinelt.
Discrete Appl. Math. 156:3 (2008), 368384.
 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), 385396.
 On the graphical relaxation of the symmetric traveling salesman polytope.
With M. Oswald and G. Reinelt.
Math. Program. Ser. B 110 (2007), 175193.
 A note on the Undirected Rural Postman Problem polytope.
With G. Reinelt
Math. Program. Ser. A 106:3 (2006), 447452.
 Transformation of facets of the General Routing Problem polytope.
With G. Reinelt.
SIAM J. Optim. 16:1 (2005), 220234.
In Conference Proceedings (top tier refereed conferences)
 Foolingsets and rank in nonzero characteristic (extended abstract).
With M. Friesen (Magdeburg)
Proceedings of EuroComb (2013) 383390 (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 LatinAmerican Algorithms, Graphs and Optimization Symposium
Electron. Notes Discrete Math. 35 (2009), 311316
 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 seriesparallel 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
OttovonGuericke University of Magdeburg
 Algorithms with random input and statistical mechanics
 Probabilistic Methods in Combinatorics
Heidelberg University
 Fourieranalytic Methods in Combinatorics
 Combinatorics
Undergraduate Research
 Researchoriented 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 31improper 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 edgelabelings 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)
 2year 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 invitationonly conferences, or at conferences with a competitive selection process. (Contributed talks at openparticipation conferences w/o competitive selection are not listed.)
I have given up writing these down.
 Sep 2013: EuroComb'13. Fooling sets and rank in nonzero characteristic. (slides)
 July 2013: International Conference on Continuous Optimization, Lisbon, Portugal. Invited talk in the session organized by J. Gouveia and R. Thomas.
Supportbased 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: CologneTwente Workshop on Graphs and Combinatorial Optimization, Enschede, NL. Fooling sets and rank in nonzero 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 GTSPFacet defines an STSPFacet.
 Oct 2004: University of Valencia, Valencia, Spain.
Invited talks Separation of some constraints for routing problems
A survey of the cuttingplane 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/3Marathon 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 