**October 15, 2013, 4:00pm**

*Johnson 175*

**James Pfeiffer**, *Department of Mathematics, University of Washington*

**A Criterion for Sums of Squares on the Hypercube**

Abstract: Functions on the hypercube $\{0,1\}^n$ have a natural notion of polynomial divisibility and degree. We use the action of the symmetric group to show that a function vanishing to odd degree on a slice of the hypercube given by $\sum_i x_i = t$, for $t \le n/2$, cannot be a sum of squares of degree $d \le t$. As a corollary, we reprove a result of Laurent that the Lasserre rank of optimizing over the cut polytope is at least $n/2$. We also find a nonnegative degree-4 polynomial on $\RR^n$ which requires degree-$n/2$ sum of squares multipliers to be written as a sum of squares.