Symmetric Sums of Squares Over k-Subset Hypercubes

Annie Raymond - University of Massachusetts

April 13, 2018, 2:30 p.m. - April 13, 2018, 3:30 p.m.

ENGMC 103

Hosted by: Hamed Hatami

---

Polynomial optimization over hypercubes has important applications in combinatorial optimization. We develop a symmetry-reduction method that finds sums of squares certificates for non-negative symmetric polynomials over k-subset hypercubes that improves on a technique due to Gatermann and Parrilo. For every symmetric polynomial that has a sos expression of a fixed degree, our method finds a succinct sos expression whose size depends only on the degree and not on the number of variables.  Our results relate naturally to Razborov's flag algebra calculus for solving problems in extremal combinatorics. This leads to new results involving flags and their power in finding sos certificates. This is joint work with James Saunderson, Mohit Singh and Rekha Thomas.

Annie Raymond is an assistant professor at the University of Massachusetts in Amherst. Originally from Montreal, she studied math and music at MIT as an undergrad before pursuing a Ph.D. in mathematics at the Technische Universitaet in Berlin and a postdoc at the University of Washington. At any given moment, you will most likely find her thinking about extremal graph theory and sums of squares---perhaps while riding her bicycle or playing the piano---or reflecting on education in prisons, on how to increase diversity in STEM and on how to bake the perfect sourdough.