Extended Formulations 3
summary
Extension complexity equals non-negative rank of the slack matrix, and for the correlation polytope LP/SDP relaxations correspond to families or vector spaces of functions on the hypercube. Imposing vertex-permutation symmetry forces those families to be invariant, which group-theory classifies as juntas plus functions of the Hamming weight. Using an integrality-gap instance for Sherali–Adams and a complement-substitution trick, the talk derives explicit lower bounds: small symmetric lifts cannot express the required slack functions, so symmetric extended formulations fail at compact approximation.
AI-written summary · about