| Résume | To describe a polytope $P$ in $\R^d$, one needs to know either the list of all its vertices, or a complete set of affine inequalities which characterize $P$. When both are known, it gives us a non-negative matrix $S$, called the slack matrix of $P$. Having a short enough list of affine inequalities to describe $P$ is useful, for optimization purposes. This has motivated the search for compact formulations of $P$, i.e. affine extensions whose size (=number of inequalities to describe it) is much smaller than that of $P$, and the search for barriers to the existence of compact formulations ([Rothvoss17]). The extension complexity of a polytope $P$, denoted xc(P), is defined as the smallest size of an affine extension $Q$ of $P$. In the seminal paper [Yannakakis91], M. Yannakakis characterizes xc(P) as the non-negative rank of the slack matrix $S$ of $P$ (we will define $S$ in the talk). Another characterization of xc(P) is possible via randomised protocols, as shown in ([Faenza et al. 2012]).
Among all extensions $Q$, some of them respect the symmetries of $P$, they are called symmetric extensions. The symmetric extension complexity, xc_{sym}(P), is defined as the smallest size of a symmetric extension. We define a notion of symmetric randomised protocols for a given polytope $P$. We show that, at the cost of allowing unbounded arity in the protocols, and focusing on space complexity instead, as in [Faenza et al. 2012], the smallest complexity of a symmetric protocol computing some slack matrix of P, equals xc_{sym}(P). We will illustrate the various notions of protocols with two examples, namely the perfect matching polytope and the spanning tree polytope. |
