Publications

Orcid DBLP Google Scholar

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

  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