  Yannakakis showed that the matching problem does not have a small symmetric
linear program. Rothvo{\ss} recently proved that any, not necessarily
symmetric, linear program also has exponential size. It is natural to ask
whether the matching problem can be expressed compactly in a framework such as
semidefinite programming (SDP) that is more powerful than linear programming
but still allows efficient optimization. We answer this question negatively for
symmetric SDPs: any symmetric SDP for the matching problem has exponential
size.
  We also show that an O(k)-round Lasserre SDP relaxation for the metric
traveling salesperson problem yields at least as good an approximation as any
symmetric SDP relaxation of size $n^k$.
  The key technical ingredient underlying both these results is an upper bound
on the degree needed to derive polynomial identities that hold over the space
of matchings or traveling salesperson tours.
