Summer Graduate School

Graph of the Motzkin polynomial, which is nonnegative but not a sum of squares.

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 combinatorics. 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.

Suggested prerequisites

We will assume thorough familiarity with some topics in algebra on the level of a first year graduate sequence in Algebra. In particular, the students should be familiar with groups, rings and ideals, quotients, etc. A concrete source for the needed background are Appendices 1 and 4 in the book Semidefinite Optimization and Convex Algebraic Geometry, (Editors: Grigoriy Blekherman, Pablo A. Parrilo and Rekha R. Thomas, MOS-SIAM Series on Optimization 13 , 2012.) Familiarity with any of representation theory, real algebraic geometry, convex geometry, graph theory or semidefinite optimization is a plus but will not be assumed. Students should prepare by reading Appendices 2 and 3 in that same book.

Due to the small number of students supported by MSRI, only one student per institution will be funded by MSRI.

For eligibility and how to apply, see the Summer Graduate Schools homepage