Annie Raymond: Symmetric Sums of Squares over k-subset hypercubes
Tid: Må 2018-03-12 kl 12.00
Föreläsare: Annie Raymond, University of Massachusetts Amherst
Plats: Room 4523, Lindstedtsvägen 5, KTH
Lunch is served at 12:00 noon (register atat the latest the Saturday before, but preferably earlier). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for 1½-2 hours of more technical discussions.
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.