Small Extended Formulations for Cyclic Polytopes

Understand

We provide an extended formulation of size O(log n)^{\lfloor d/2 \rfloor} for the cyclic polytope with dimension d and n vertices (i,i^2,\ldots,i^d), i in [n].

• First, we find an extended formulation of size log(n) for d= 2.
• Then, we use this as base case to construct small-rank nonnegative factorizations of the slack matrices of higher-dimensional cyclic polytopes, by iterated tensor products.
• Through Yannakakis's factorization theorem, these factorizations yield small-size extended formulations for cyclic polytopes of dimension d>2.