Georgia Institute of Technology College of Sciences

Yannakakis showed that the matching problem does not have a small symmetric linear program. Rothvoß 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 (TSP) 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. This is joint work with Jonah Brown-Cohen, Prasad Raghavendra and Benjamin Weitz from Berkeley, and Gabor Braun, Sebastian Pokutta, Aurko Roy and Daniel Zink at Georgia Tech.

We consider fibered holomorphic dynamics, generated by a skew product over an irrational translation of the torus. The invariant object that organizes the dynamics is an invariant torus. Often one can find an approximately invariant torus K_0, and we construct an invariant torus, starting from K_0. The main technique is a KAM iteration in a-posteriori format. The asymptotic properties of the derivative cocycle A_K play a crucial role: In this first talk we will find suitable geometric and number-theoretic conditions for A_K. Later, we will see how to relax these conditions.