**This page is out-dated.**For current updates see my official homepage at the Algorithms & Theory group in Tartu.

## Résumé

2/13-now | Senior Lecturer |

University of Tartu (Wikipedia), Estonia | |

5/12 | Habilitation* in Mathematics |

6-7/11 | Visiting Prof |

Brock University, St.Catharines, ON | |

5/09-2/13 | PostDoc / Priv.-Doz.* |

Otto von Guericke University Magdeburg, Germany | |

3/07-4/09 | PostDoc |

Université Libre de Bruxelles (ULB), Brussels, Belgium | |

1/06-2/07 | PostDoc in Heidelberg |

12/05 | PhD in Mathematics (summa cum laude) |

Ruprecht Karls University of Heidelberg, Germany |

## Research

My research is in**Discrete Mathematics**, more specifically combinatorics, random structures, combinatorial optimization, and algorithms.

Here are some slides of recent talks I've given about my research.

- Nondeterministic Communication Complexity of random 01 matrices
- Fooling-Sets and Rank in Non-Zero Characteristic
- Support-based lower bounds for the positive semidefinite rank of a nonnegative matrix

## List of Publications

My preprints are on the arXiv (since about 2008): http://arxiv.org/a/theis_d_1

###
**In preparation**

- On the satisfiability of random regular signed SAT formulas.

With K. Ballerstein (ETHZ) and C. Laus (Magdeburg).

###
**Submitted**

*Support based lower bounds for the positive semidefinite rank of nonnegative matrices.*

With Troy Lee (CQT, Singapore).

**Linear Algebra Appl.**(arXiv:1203.3961)*Good edge-labelings and graphs with girth at least five.*

With M. Bode (Magdeburg) & B. Farzad (Brock University, ON).

**Discrete Math. Theor. Comput. Sci.**(arXiv:1109.1125)

###
**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 $K_5\setminus 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 (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)

###
**In Conference Proceedings (non-refereed)**

*The chromatic number of random lifts of $K_5\setminus 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 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)*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 (2008)- The Cops & Robber game on series-parallel graphs. (short communication)

###
**Theses**

- Ph.D. Thesis

*Polyhedra and Algorithms for the General Routing Problem.*(Dec 2005) - Habilitationsschrift (cumulative)

*Polyhedral and Combinatorial Aspects in Optimization.*(May 2012)

## Teaching

###
**Courses**

**University of Tartu**

Fall 2014/5:

*Discrete Mathematics*(Compulsory for 1st year CS grad, 6 ECTS)*Extremal Combinatorics*(PhD students, 6 ECTS)

*Randomness in Computer Science*(CS grad, 6 ECTS)*Problem Solving: Hypergraph theory*(Math/CS grad, 6 ECTS)

*Discrete Mathematics*(Compulsory for 1st year CS grad, 6 ECTS)*Enumerative combinatorics*(PhD students, 6 ECTS)

*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:
- Abdullah Makkeh (PhD student, MSc Beirut)
- Mozhgan Pourmoradnasseri (PhD student, BSc Sharif, MSc Zanjan)

- 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)

## 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*

## 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.)

- 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.

## 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) |