Joint MSRI-BIRS Graduate Summer School - Sums of Squares Method in Geometry, Combinatorics and Optimization (22ss199)


(Georgia Tech)

Annie Raymond (University of Massachusetts)

Rekha Thomas (University of Washington)


The Banff International Research Station will host the "Sums of Squares Method in Geometry, Combinatorics and Optimization" Graduate Summer School in Banff from July 31 to August 12, 2022.

The study of nonnegative polynomials and sums of squares is a classical area of real algebraic geometry dating back to Hilbert’s 17th problem. It also has rich connections to real analysis via duality and moment problems. In the last 15 years, sums of squares relaxations have found a wide array of applications from very applied areas (e.g., robotics, computer vision, and machine learning) to theoretical applications (e.g., extremal combinatorics, theoretical computer science). Also, an intimate connection between sums of squares and classical algebraic geometry has been found. Work in this area requires a blend of ideas and techniques from algebraic geometry, convex geometry and representation theory. After an introduction to nonnegative polynomials, sums of squares and semidefinite optimization, we will focus on the following three topics:

• Sums of squares on real varieties (sets defined by real polynomial equations) and connections with classical algebraic geometry.

• Sums of squares method for proving graph density inequalities in extremal combina- torics. Here addition and multiplication take place in the gluing algebra of partially labelled graphs.

• Sums of squares relaxations for convex hulls of real varieties and theta-bodies with applications in optimization.

The summer school will give a self-contained introduction aimed at beginning graduate students, and introduce participants to the latest developments. In addition to attending the lectures, students will meet in intensive problem and discussion sessions that will explore and extend the topics developed in the lectures. The problem sessions are a crucial part of the Summer School and will be led by both lecturers and TAs.

• Math Subject Classification numbers: 14P99, 52A20, 05D99 ( msc/msc2010.html)

• Keywords: sums of squares, semidefinite programming, optimization, real algebraic geometry, combinatorics, representation theory

The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the U.S. National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnología (CONACYT).