3:00pm - 5:00pmStructured sums of squares
Chair(s): James Saunderson (Monash University, Australia), Mauricio Velasco (Universidad de los Andes)
A description of a nonnegative polynomial as a sum of squares gives a concise proof of its nonnegativity. Computationally, such sum-of-squares decompositions are appealing because we can search for them by solving a semidefinite feasibility problem. This connection means that optimization and decision problems arising in a range of areas, from robotics to extremal combinatorics, can be reformulated as, or approximated with, semidefinite optimization problems.
This minisymposium highlights the roles of various kinds of additional structures, including symmetry and sparsity, in understanding when (structured) sum of squares decompositions do and do not exist. It will also showcase interesting connections between sums of squares and a range of areas, such as extremal combinatorics, logic, dynamical systems and control, and algorithms and complexity theory.
(25 minutes for each presentation, including questions, followed by a 5-minute break; in case of x<4 talks, the first x slots are used unless indicated otherwise)
Simple Graph Density Inequalities with no Sum of Squares Proofs
Annie Raymond1, Greg Blekherman2, Mohit Singh2, Rekha Thomas3
1University of Massachusetts Amherst, 2Georgia Institute of Technology, 3University of Washington
Establishing inequalities among graph densities is a central pursuit in extremal combinatorics. One way to certify the nonnegativity of a graph density expression is to write it as a sum of squares. In this talk, we identify a simple condition under which a graph density expression cannot be a sum of squares. Using this result, we prove that the Blakley-Roy inequality does not have a sum of squares certificate when the path length is odd. We also show that the same Blakley-Roy inequalities cannot be certified by sums of squares using a multiplier of the form one plus a sum of squares. These results answer two questions raised by Lovász. Our main tool is used again to show that the smallest open case of Sidorenko's conjectured inequality cannot be certified by a sum of squares. This is joint work with Greg Blekherman, Mohit Singh and Rekha Thomas.
Symmetry and Nonnegativity
Greg Blekherman
Georgia Institute of Technology
I will discuss several recent results on symmetric nonnegative polynomials and their approximations by sums of squares. I will consider several types of symmetry, but the situation is especially interesting in the limit as the number of variables tends to infinity. There are diverse applications to quantum entanglement, graph density inequalities and theoretical computer science.
Symmetry and the Sum of Squares Hierarchy
Aaron Potechin
University of Chicago
In this talk, I will describe how symmetry can be used both to greatly reduce the size of the semidefinite program needed to implement SOS and to make proving SOS lower bounds considerably easier. In particular, I will describe how to construct semidefinite programs for SOS on symmetric problems whose size is independent of n using Razborov's flag algebras. I will also describe a sufficient condition for proving SOS lower bounds when the problem is symmetric.
As an application, I will describe SOS lower bounds for the following Turan-type problem: What is the minimum possible number of triangles in a graph G with n vertices? More generally, I will describe how we can obtain SOS lower bounds almost automatically whenever our problem is symmetric and the difficulty of our problem comes from integrality arguments (i.e. arguments that a certain expression must be an integer).
Note: This talk will be based on the paper "Symmetric Sums of Squares over k-Subset Hypercubes" by Raymond, Saunderson, Singh, and Thomas and my paper "Sum of Squares Lower Bounds from Symmetry and a Good Story".
