CMSC 39600 1 (Autumn 2018) Topics in Theoretical Computer Science: The Sum of Squares Hierarchy

CMSC 39600 1 (Autumn 2018) Topics in Theoretical Computer Science: The Sum of Squares Hierarchy

Instructor: Aaron Potechin

Crerar Office #237


Course Times: Tuesdays and Thursdays from 12:30 to 1:50 in Pick Hall 22.


Office Hours: Mondays from 3-4 or by appointment.


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 basic algebra 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 we've learned so far. Topics which will be covered include semidefinite programming, Positivstellensatz 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.


Course Goals: After passing the course, the student should
1. Have a deep understanding of the fundamental ideas of SOS, including semidefinite programming, duality, pseudo-expectation values, and Positivstellensatz proofs.
2. Be able to apply SOS on small instances of problems.
3. Know the major results on SOS.
4. Have a sense of current research on SOS and what the major open problems are.


Linear algebra will be used throughout the course. Mathematical maturity will also be very helpful as this course will touch on many topics in mathematics and theoretical computer science.


Course Materials: Lecture notes and supplemental readings. Lecture notes can be found under Files.

Grades will be based on 5 problem sets with an optional class project for extra credit. Listeners are welcome.


Lateness policy: Late problems sets will be accepted for full credit if you have prior approval from me or a note from student services. Otherwise, late problem sets will be accepted for partial credit until the solutions are posted.


Collaboration Policy: Collaboration is on problem sets is allowed as long as you name your collaborators and write up the solutions individually.



Lecture 1: Introduction to the Sum of Squares Hierarchy

Lecture 2: Linear Programming and Duality

Lecture 3: Semidefinite Programming

Lecture 4: Goemans-Williamson

Lecture 5: SOS Proofs and the Motzkin Polynomial

Lecture 6: Linear Programming for Sparsest Cut

Lecture 7: Arora-Rao-Vazirani

Lecture 8: SOS Lower Bound for 3-XOR

Lecture 9: SOS Lower Bound for Knapsack

Lecture 10: Gadget Reductions and SOS

Lecture 11: Discrete Fourier Analysis and Graph Matrices

Lecture 12: Norm Bounds on Graph Matrices

Lecture 13: SOS Lower Bounds for Planted Clique Part I

Lecture 14: SOS Lower Bounds for Planted Clique Part II

Lecture 15: Planted Sparse Vector

Lecture 16: Exact Tensor Completion

Lecture 17: The Unique Games Conjecture and Hardness of Approximation for MAX CUT.

Lecture 18: Subexponential Time Algorithm for Unique Games and Small Set Expansion

Lecture 19: Open Problems

Course Summary:

Date Details