On the linear extension complexity of regular n-gons

In this paper, we propose new lower and upper bounds on the linear extension complexity of regular n-gons. Our bounds are based on the equivalence between the computation of (i) an extended formulation of size r of a polytope P, and (ii) a rank-r nonnegative factorization of a slack matrix of the polytope P. The lower bound is based on an improved bound for the rectangle covering number (also known as the boolean rank) of the slack matrix of the n-gons. The upper bound is a slight improvement of the result of Fiorini, Rothvoss and Tiwary (2012) [9]. The difference with their result is twofold: (i) our proof uses a purely algebraic argument while Fiorini et al. used a geometric argument, and (ii) we improve the base case allowing us to reduce their upper bound 2⌈log2⁡(n)⌉ by one when 2k−1