# Publications

### Refereed Journals

**Extension Complexity of Formal Languages**

Theory of Computing Systems, 2019**Polynomial size linear programs for problems in \(P\)**

with David Avis, David Bremner, and Osamu Watanabe

Discrete Applied Mathematics, Vol. 265, 2019, pp 22-39**Compact linear programs for 2SAT**

with David Avis

European Journal of Combinatorics, Vol. 80, 2019, pp 17-22**Parametrized Extension Complexity of Independent Set and Related Problems**

with Jakub Gajarský and Petr Hliněný

Discrete Applied Mathematics, Vol. 248, 2018, pp 56-67**Extension complexities of Cartesian products involving a pyramid**

with Stefan Weltge and Rico Zenklusen

Information Processing Letters, Vol. 128, 2017, pp 11-13**On the \(\mathcal{H}\)-Free Extension Complexity of the TSP**

with David Avis

Optimization Letters, Vol. 11(3), 2017, pp 445-455**A generalization of extension complexity that captures \(P\)**

with David Avis

Information Processing Letters, Vol. 115(6-8), 2015, pp 588-593**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**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**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**On the extension complexity of combinatorial polytopes.**

with David Avis

Math. Prog. Series B, Vol. 153(1), 2015, pp 95-115**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**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**On the largest convex subsets in Minkowski sums**

Information Processing Letters, Vol. 114(8), 2014, pp 405-407**Extended formulations for polygons**

with Samuel Fiorini and Thomas Rothvoß

Discrete & Computational Geometry, Vol. 48, No. 3, 2012, pp 658-668**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**Complexity of Approximating the Vertex Centroid of a Polyhedron**

with Khaled Elbassioni

Theoretical Computer Science, Vol. 421, 2012, pp 56-61**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**On a Cone Covering Problem**

with Khaled Elbassioni

Computational Geometry: Theory and Applications, Volume 44, No. 3, 2011, pp 129-134**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

**Extension Complexity, MSO Logic, and Treewidth**

with Petr Kolman and Martin Koutecký

SWAT 2016, pp 18:1-18:14**On the extension complexity of combinatorial polytopes.**

with David Avis

ICALP 2013, pp 57-68**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**Extended formulations, non-negative factorizations and randomized communication protocols**

with Yuri Faenza, Samuel Fiorini, and Roland Grappe

ISCO 2012, pp 129-140**On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems**

with Christian Knauer, Daniel Werner

STACS 2011, pp 649-660**Complexity of Approximating the Vertex Centroid of a Polyhedron**

with Khaled Elbassioni

ISAAC 2009, pp 413-422**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**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**On the hardness of minkowski addition and related operations**

Symposium on Computational Geometry 2007, pp 306-309**On Computing the Centroid of the Vertices of an Arrangement and Related Problems**

with Deepak Ajwani, Saurabh Ray, and Raimund Seidel

WADS 2007, pp 519-528

### Preprints

**On computing the Shadows and Slices of a Polytope**

Preprint, April 2008, 11 pages, CoRR abs/0804.4150**On the extension complexity of scheduling**

with Victor Verdugo, and Andreas Wiese

Preprint, Feb. 2019, 17 pages, CoRR abs/1902.10271**Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach.**

with Lars Jaffke, and Mateus de Oliveira Oliveira

Preprint, Jan. 2020, 19 pages, CoRR abs/2001.05583