Mathematical Sciences Research Institute

Home » Workshop » Schedules » Symmetric Sums of Squares over k-Subset Hypercubes

Symmetric Sums of Squares over k-Subset Hypercubes

Geometric and topological combinatorics: Modern techniques and methods October 09, 2017 - October 13, 2017

October 10, 2017 (11:00 AM PDT - 12:00 PM PDT)
Speaker(s): Annie Raymond (University of Massachusetts Amherst)
Location: MSRI: Simons Auditorium
  • sums of squares

  • symmetric group

  • flag algebras

  • extremal combinatorics

Primary Mathematics Subject Classification
Secondary Mathematics Subject Classification No Secondary AMS MSC



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.

29704?type=thumb Raymond Notes 458 KB application/pdf Download
Video/Audio Files


H.264 Video 6-Raymond.mp4 241 MB video/mp4 rtsp://videos.msri.org/data/000/029/580/original/6-Raymond.mp4 Download
Buy the DVD

If none of the options work for you, you can always buy the DVD of this lecture. The videos are sold at cost for $20USD (shipping included). Please Click Here to send an email to MSRI to purchase the DVD.

See more of our Streaming videos on our main VMath Videos page.