Polytopes associated with combinatorial optimization problems (i.e., the convex hulls of the incidence vectors of the feasible solutions) in most cases have exponentially many facets. Thus, they can only be represented as the sets of solutions to exponentially large systems of linear inequalities.

One approach to reduce the size of these descriptions which I want to explore in my PhD project is to allow for representations as projections of higher dimensional semi-algebraic sets, thus to combine the concepts of extended formulations and polynomial representations, and to study the principal possibilities of obtaining short extended polynomial representations of polytopes associated with combinatorial optimization problems.

The ultimate goal of such investigations of nonlinear representations of reduced complexity would be to gain additional insights into the geometry and combinatorics of the underlying problems which remain hidden when restricting to linear representations. With respect to eventually exploiting such insights algorithmically, particular attention will be given to the question for the existence of small representations via specially structured semi-algebraic sets such as spectrahedra.