Logo

Mathematical Sciences Research Institute

Home »  Sums of Squares Method in Geometry, Combinatorics and Optimization

Summer Graduate School

Sums of Squares Method in Geometry, Combinatorics and Optimization July 13, 2020 - July 24, 2020
Parent Program: --
Location: MSRI: Simons Auditorium, Atrium
Organizers LEAD Grigoriy Blekherman (Georgia Institute of Technology), Annie Raymond (University of Massachusetts Amherst), Rekha Thomas (University of Washington)
Description
Image
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.

 

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

Keywords and Mathematics Subject Classification (MSC)
Tags/Keywords
  • sums of squares

  • semidefinite programming

  • optimization

  • real algebraic geometry

  • combinatorics

  • Representation theory

Primary Mathematics Subject Classification
Secondary Mathematics Subject Classification No Secondary AMS MSC
Funding & Logistics Show All Collapse

Show MSRI Collegiality Statement

Show Directions to Venue

Show Visa/Immigration

Show Reimbursement Guidelines

Show MSRI Collegiality Statement