Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Symmetric Sums of Squares

Special Events

Speaker: Annie Raymond, University of Washington
Location: 1147 MSB
Start time: Fri, Feb 3 2017, 4:10PM

We consider the problem of finding sum of squares (sos) expressions to
establish the non-negativity of a symmetric polynomial over a discrete 
hypercube whose coordinates are indexed by k-element subsets of
[n]. We develop a variant of the Gatermann-Parrilo symmetry-reduction
method tailored to our setting that allows for several simplifications and
a connection to Razborov's flag algebras. We show that every symmetric
polynomial that has a sos expression of a fixed degree also has a succinct
sos expression whose size depends only on the degree and not on the number
of variables. This is joint work with James Saunderson, Mohit Singh and
Rekha Thomas.