Return to Colloquia & Seminar listing
Symmetric Sums of SquaresSpecial Events
|Speaker:||Annie Raymond, University of Washington|
|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.