James Pfeiffer; A Criterion for Sums of Squares on the Hypercube

October 15, 2013, 4:00pm
Johnson 175
James Pfeif­fer, Depart­ment of Math­e­mat­ics, Uni­ver­sity 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.

Leave a Reply

Your email address will not be published. Required fields are marked *