[Theory] Topics course in Theoretical Computer Science: The Sum of Squares Hierarchy

[Aaron Potechin]

Hi everyone,

As a heads up, this quarter I am teaching my course on the sum of squares hierarchy, which is my research specialty. While there is some linear and semidefinite programming involved, the material is primarily theoretical and the only prerequisite is linear algebra. The course description is below.

Best,
Aaron

Course Title: Topics in Theoretical Computer Science: The Sum of Squares Hierarchy
Course Times: MW 4:30-5:50 in Ryerson 251


Course Description:

The sum of squares hierarchy (SoS) is a hierarchy of semidefinite programs which is broadly applicable, surprisingly powerful, and in some sense, simple. In particular, SoS can be applied to almost any combinatorial optimization problem and captures the best known algorithms for several of these problems including max cut, sparsest cut, and unique games. However, at its heart, all SoS is using is polynomial equalities and the fact that squares are non-negative over the real numbers.



The goal of this course is to give a good intuition for SoS by describing much of what is known so far about SoS. Topics which will be covered include semidefinite programming, Positivstellensatz/SoS proofs, pseudo-expectation values, the Goemans-Williamson algorithm for max cut, linear and semidefinite programs for sparsest cut, applications of SoS to planted sparse vector and tensor completion, SoS lower bounds for 3-XOR, knapsack, and planted clique, the unique games conjecture, and the small-set expansion hypothesis.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20210927/a07b8111/attachment.html>