Retour aux activités
Séminaire du GERAD

Symmetric sums of squares

iCalendar

31 août 2016   15h45 — 17h00

Annie Raymond University of Washington, États-Unis

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.


Entrée gratuite.
Bienvenue à tous!

Guy Desaulniers responsable

Lieu

Salle 4488
Pavillon André-Aisenstadt
Campus de l'Université de Montréal
2920, chemin de la Tour Montréal QC H3T 1J4 Canada