Characterizing symmetric extensions via symmetric randomised protocols, a specialization of Faenza's correspondence

Speaker: Maud Szusterman

Room: B508

Date: 27/05/2024 14:00

Abstract:

In combinatorial optimization, the extension complexity of a polytope P is defined as the minimal number of facets of an affine extension of P, which corresponds to the minimal number of affine inequalities needed to describe P, if projections are allowed. In a seminal paper (1991), Yannakakis proved that this number coincides with the non-negative rank of the slack matrix of P. In 2011, Faenza et al. proved that its logarithm coincides with the minimal height of a randomised protocol computing (or rather: guessing) the entries of a slack matrix of P. Remaining in the language of communication complexity, but focusing on the number of rounds (of communication) rather than on the number of bits exchanged between the two parties, we further introduce a notion of symmetry within protocols -which we illustrate with the example of the perfect matching polytope ; and show a correspondence between symmetric protocols and symmetric extensions of P. This enables us to characterize the G-symmetric extension complexity of a polytope P.