The sum of squares hierarchy, a hierarchy of semidefinite programs, is an exciting frontier of complexity theory and proof complexity which is broadly applicable, surprisingly powerful, and in some sense, simple. The sum of squares hierarchy is broadly applicable as it can be applied to any system of polynomial equations over the real numbers; most problems of interest can be expressed in this form. The sum of squares hierarchy is powerful; it captures the best known algorithms for several combinatorial optimization problems including max cut, sparsest cut, and unique games. Finally, the sum of squares is in some sense simple; all it is really using is the fact that squares are nonnegative over the real numbers.
The goal of this seminar is to give a good intuition for the sum of squares hierarchy by describing much of what we've learned thus far. Topics which will be covered include semidefinite programming, Positivstellensatz proofs, applications of sum of squares to max cut, sparsest cut, planted sparse vector, and tensor completion, pseudo-expectation values, sum of squares lower bounds for 3-XOR, knapsack, and planted clique, the unique games conjecture, and the small-set expansion hypothesis.
This seminar will consist of lectures and student presentations in the last few weeks of of the course. This seminar will be given in English.
Linear algebra will be used throughout the seminar. Mathematical maturity will also be very helpful as this seminar will touch on many topics in mathematics and theoretical computer science.
After passing the course, the student should
Pass/Fail or Listener. 70% of the grade will be based on the problem sets (which include the programming assignments) and 30% of the grade will be based on the class presentation
Thursday 2-3 in Room 1527