Symmetric Sums of Squares over k-Subset Hypercubes
Host
Department of Applied Mathematics
Speaker
Annie Raymond, Acting Assistant Professor
Department of Mathematics, University of Washington
http://www.math.washington.edu/~raymonda/
Description
The speaker considers 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]. The speaker develops 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. The speaker shows 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.
Event Topic
Nonlinear Algebra and Statistics (NLASTATS)