New time slot: Wednesdays from 10 to 12 starting April 22!
First (organizational) meeting is Tuesday, April 14, at 14:15 in the Seminar room of the Villa (Arnimallee 2). Topics will be assigned there.
The extension complexity of a polytope P is the minimal number of facets of a polytope Q that linearly projects onto P. This rather simple definition has interesting consequences and relations to areas such as discrete geometry, combinatorial optimization, information theory, and linear algebra. Determining the extension complexity of a polytope is extremely hard (even for polygons!) and obtaining exact values or even just bounds for special polytopes is an active area of research. The goal of the seminar is to develop a good understanding of extension complexity and the notions related to it. Topics might include:
Language: English/German
Extension complexity |
|||
| When | Who | What | References |
|---|---|---|---|
| 21.04.2015 | Katy | Extended formulations and cone factorizationsAn extended formulation of a polytope is any polytope that linearly projects onto it. This extension induces a non-negative factorization of its slack matrix. More generally, one can consider a polytope as the projection of an affine slice of a cone (for example the non-negative cone, or the cone of psd matrices), which also induces a factorization. The minimal size of such factorization is an affine invariant of the polytope, which can have very different behaviors under the combinatorial type, as polygons already show. |
|
| When | Who | What | References |
| 28.04.2015 | Alex | Small extended formulationsA first example of a polytope that admits very small extensions is the permutahedron. The n-1 dimensional permutatahedron has 2^n-2 facets. But it is easily seen to be a projection of the Birkhoff polytope, which is defined by n^2 inequalities. Even more, it has an extension with order of n log(n) facets, which is asymptotically optimal. The methods to construct these extensions extend to generate extensions of other symmetric polytopes. |
|
| 06.05.2015 | Josué | Symmetry mattersIn a breakthrough from 1991, Yannakakis proved that there is no symmetric extended formulation of the TSP polytope of polynomial size. He also conjectured that there is no extension without the symmetry constraint, although there was no complete proof of this statement until 2012. Indeed, symmetry matters in general, and there are symmetric polytopes that only asymmetric small extensions. |
|
| 13.05.2015 | Max | There are 0/1 polytopes with large extension complexityAn elegant counting argument shows that there exist polytopes in R^n, all whose coordinates are 0 or 1, that have exponential extension complexity (although does not provide specific examples). |
|
| 20.05.2015 | Giulia | Lower bounds for extension complexityA longstanding open question asked whether the TSP polytope admitted an extended formulation of polynomial size. The answer is no. One way to find lower bounds for the extension complexity of a polytope is through the rectangle covering number of its slack matrix. |
|
Non-negative factorizations |
|||
| When | Who | What | References |
| 27.05.2015 | Milan | Communication complexityAnother interesting interpretation of extension complexity is given in terms of communication protocols. For example, a protocol for the clique vs stable set problem allowed Yannakakis to construct small extended formulations for the stable set polytopes of perfect graphs. |
|
| 03.06.2015 | Björn | Geometry of nonnegative factorizationsNonnegative factorizations of nonnegative matrices that are not slack matrices of polytopes also have a nice geometric interpretation in terms of nested polytopes. |
|
SDP-rank |
|||
| When | Who | What | References |
| 10.06.2015 | Marek | Introduction to spectrahedraA spectrahedron is an affine slice of the cone of positive-semidefinite matrices. The same way as polyhedra are feasible regions of linear programs, spectrahedra are feasible regions of semidefinite programs. |
|
| 24.06.2015 | Svenja | PSD-minimal polytopesThe PSD-rank of a d-polyope is always at least d+1. Which are the polytopes that attain this bound? |
|