[Colloquium] Theory talk this afternoon

[Alexander Razborov via Colloquium]

REMINDER:

Departments of Computer Science & Mathematics
Combinatorics & Theoretical Seminar

Today, Tuesday, September 13, 2016
3:00 pm
Ryerson 251

Annie Raymond
University of Washington
Title: “Symmetric Sums of Squares over $k$-Subset Hypercubes”

Abstract: 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. 

Host: Prof. Alexander Razborov

*Refreshments will be served prior to the talk in Ryerson 255 @ 2:30 pm*

_______________________________________________
Colloquium mailing list  -  Colloquium at mailman.cs.uchicago.edu
https://mailman.cs.uchicago.edu/mailman/listinfo/colloquium
_______________________________________________
faculty mailing list  -  faculty at mailman.cs.uchicago.edu
https://mailman.cs.uchicago.edu/mailman/listinfo/faculty
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20160913/d7ac4b19/attachment.html>