Sum of Squares Summer Course

These are some (draft) lecture notes and homework exercises from a July 2014 course on the Sum of Squares method from a theoretical computer science perspective. Both lecture notes and homework exercises are somewhat rough, and may contain bugs/typos.

• Homework 0 - prework
• Lecture 1 - introduction
• Lecture 2 - max cut and sparsest cut
• Homework 1
• Lecture 3 - lower bound for random 3XOR
• Homework 2
• Lecture 4 - Finding a planted sparse vector in a subspace
• Lecture 5 - Dictionary learning via the SOS method
• Homework 3
• Lecture 6 - Sparsest cut and the ARV algorithm
• Lecture 7 - SOS lower bounds for the planted clique problem.
• Lecture 8 - musings on SOS vs the Unique Games Conjecture (no notes yet)