Conference abstracts

Session A2 - Computational Algebraic Geometry - Semi-plenary talk

July 10, 14:30 ~ 15:20

Symmetric sums of squares over $k$-subset Hypercubes

Rekha Thomas

University of Washington, USA   -   rrthomas@uw.edu

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 in a finite setting, an angle that had not been explored before.

Joint work with Annie Raymond (University of Washington, USA), James Saunderson (Monash University, Australia) and Mohit Singh (Georgia Institute of Technology, USA).

View abstract PDF



FoCM 2017, based on a nodethirtythree design.