Publications

Orcid DBLP Google Scholar

Refereed Journals

  1. Extension Complexity, MSO Logic, and Treewidth
    with Petr Kolman and Martin Koutecký
    Discret. Math. Theor. Comput. Sci. Vol. 22(4), 2020
  2. Extension Complexity of Formal Languages
    Theory of Computing Systems, Vol. 64(5), 2020, pp 735-753
  3. On the extension complexity of scheduling polytopes
    with Victor Verdugo, and Andreas Wiese
    Operations Research Letters, Vol. 48(4), 2020, pp 472-479

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

  5. Compact linear programs for 2SAT
    with David Avis
    European Journal of Combinatorics, Vol. 80, 2019, pp 17-22

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

  7. Extension complexities of Cartesian products involving a pyramid
    with Stefan Weltge and Rico Zenklusen
    Information Processing Letters, Vol. 128, 2017, pp 11-13

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  22. 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. On Permuting Some Coordinates of Polytopes
    ISCO 2022, pp 102--114
  2. On the Complexity of Some Facet-Defining Inequalities of the QAP-Polytope
    with Pawan Aurora
    COCOA 2020, pp 334--349
  3. Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach
    with Lars Jaffke and Mateus de Oliveira Oliveira
    MFCS 2020, pp 50:1--50:15
  4. Extension Complexity, MSO Logic, and Treewidth
    with Petr Kolman and Martin Koutecký
    SWAT 2016, pp 18:1-18:14

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

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

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

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

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

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

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

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

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

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

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