# Publications

### Refereed Journals

1. On the $$\mathcal{H}$$-Free Extension Complexity of the TSP
with David Avis
Optimization Letters, Vol. 11(3), 2017, pp 445-455

2. A generalization of extension complexity that captures $$P$$
with David Avis
Information Processing Letters, Vol. 115(6-8), 2015, pp 588-593

3. Generalised probabilistic theories and conic extensions of polytopes
with Samuel Fiorini, Serge Massar, and Manas K. Patra
Journal of Physics A: Mathematical and Theoretical, Vol. 48(2), 2015, 025302

4. Exponential Lower Bounds for Polytopes in Combinatorial Optimization
with Samuel Fiorini, Serge Massar, Sebastian Pokutta, and Ronald de Wolf
Journal of ACM, Vol. 62(2), 17, 2015

5. Extended formulations, non-negative factorizations and randomized communication protocols
with Yuri Faenza, Samuel Fiorini, and Roland Grappe
Math. Prog. Series B, Vol. 153(1), 2015, pp 75-94

6. On the extension complexity of combinatorial polytopes.
with David Avis
Math. Prog. Series B, Vol. 153(1), 2015, pp 95-115

7. A Proof of the Oja-Depth Conjecture in the Plane
with Nabil H. Mustafa and Daniel Werner
Computationak Geometry: Theory & Applications, Vol. 47, No. 6, 2014, pp 668-674

8. Self-duality of Polytopes and its Relations to Vertex Enumeration and Graph Isomorphism
with Khaled Elbassioni
Graphs and Combinatorics, Vol. 30(3), 2014, pp 729-742

9. On the largest convex subsets in Minkowski sums
Information Processing Letters, Vol. 114(8), 2014, pp 405-407

10. Extended formulations for polygons
with Samuel Fiorini and Thomas Rothvoß
Discrete & Computational Geometry, Vol. 48, No. 3, 2012, pp 658-668

11. Largest Area Rectangles inside a Convex Polygon
with Christian Knauer, Lena Schlipf, and Jens M. Schmidt
Journal of Discrete Algorithms, Vol. 13, 2012, pp 78-85

12. Complexity of Approximating the Vertex Centroid of a Polyhedron
with Khaled Elbassioni
Theoretical Computer Science, Vol. 421, 2012, pp 56-61

13. The Negative Cycles Polyhedron and Hardness of Checking Some Polyhedral Properties
with Endre Boros, Khaled Elbassioni, and Vladimir Gurvich
Annals of Operations Research, Vol. 188, No. 1, 2011, pp 63-76

14. On a Cone Covering Problem
with Khaled Elbassioni
Computational Geometry: Theory and Applications, Volume 44, No. 3, 2011, pp 129-134

15. On the Hardness of Computing Intersection, Union and Minkowski Sum of Polytopes
Discrete & Computational Geometry, Vol. 40, No. 3, 2008, pp 469-479

### Refereed Conference Proceedings

1. Extension Complexity, MSO Logic, and Treewidth
with Petr Kolman and Martin Koutecký
SWAT 2016, pp 18:1-18:14

2. On the extension complexity of combinatorial polytopes.
with David Avis
ICALP 2013, pp 57-68

3. Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds
with Samuel Fiorini, Serge Massar, Sebastian Pokutta, and Ronald de Wolf
STOC 2012, pp 95-106

4. Extended formulations, non-negative factorizations and randomized communication protocols
with Yuri Faenza, Samuel Fiorini, and Roland Grappe
ISCO 2012, pp 129-140

5. On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems
with Christian Knauer, Daniel Werner
STACS 2011, pp 649-660

6. Complexity of Approximating the Vertex Centroid of a Polyhedron
with Khaled Elbassioni
ISAAC 2009, pp 413-422

7. On a Cone Covering Problem
with Khaled Elbassioni
CCCG 2008 , pp 171-174
Correction: Theorem 4 is wrong and has been removed in the Journal version

8. On the Complexity of Checking Self-duality of Polytopes and its Relations to Vertex Enumeration and Graph Isomorphism
with Khaled Elbassioni
Symposium on Computational Geometry 2008, pp 192-198

9. On the hardness of minkowski addition and related operations
Symposium on Computational Geometry 2007, pp 306-309

10. On Computing the Centroid of the Vertices of an Arrangement and Related Problems
with Deepak Ajwani, Saurabh Ray, and Raimund Seidel

### Preprints

1. On computing the Shadows and Slices of a Polytope
Preprint, April 2008, 11 pages, CoRR abs/0804.4150

2. Polynomial size linear programs for problems in $$P$$
with David Avis, David Bremner, and Osamu Watanabe
Preprint, March 2015, 17 pages, CoRR abs/1408.0807

3. Parametrized Extension Complexity of Independent Set and Related Problems
with Jakub Gajarský and Petr Hliněný
Preprint, November 2015, 20 pages, CoRR abs/1511.08841

4. Extension Complexity of Formal Languages
Preprint, March 2016, 15 pages, CoRR abs/1603.07786

5. Extension complexities of Cartesian products involving a pyramid
with Stefan Weltge and Rico Zenklusen
Preprint, Feb. 2017, 5 pages, CoRR abs/1702.01959

6. Compact linear programs for 2SAT
with David Avis
Preprint, Feb. 2017, 6 pages, CoRR abs/1702.06723

### Theses

1. Complexity of Some Polyhedral Enumeration Problems
Ph.D. Thesis, December 2008, Saarland University
Correction: Theorem 7.3.4 is wrong and should be ignored.

2. Orthogonal Range Searching
M.Sc. Thesis, December 2003, Saarland University