Symmetric Sums of Squares over k-Subset Hypercubes
Geometric and topological combinatorics: Modern techniques and methods October 09, 2017 - October 13, 2017
Location: SLMath: Eisenbud Auditorium
sums of squares
symmetric group
flag algebras
extremal combinatorics
12J20 - General valuation theory for fields [See also 13A18]
80A19 - Diffusive and convective heat and mass transfer, heat flow
6-Raymond
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.
Raymond Notes
|
Download |
6-Raymond
H.264 Video |
6-Raymond.mp4
|
Download |
Please report video problems to itsupport@slmath.org.
See more of our Streaming videos on our main VMath Videos page.