# CMU 15-859GG

**Proofs vs Algorithms: The Sum-of-Squares Method**

#####
**Instructor:** Pravesh K. Kothari (Gates 7105)

**TA:** Peter Manohar (Gates 9007)

Course Summary

**Syllabus:**
Welcome to 15-859-GG! This seminar examines the

**Prerequisites:** We will assume “mathematical maturity” and familiarity with topics that are typically covered in basic classes such as: eigen- vectors and eigenvalues, linear programming, LP duality and Farkas lemma, outline of ellipsoid method, basics of probability (expectation, variance, tail bounds), basic spectral graph theory (graphs and their adjacency matrices, relation between spectrum of adjacency matrix and random walk). Most of these ideas are covered in classes such as Theorist's Toolkit. Graduate level classes in Complexity Theory and Algorithm Design will help appreciate the content better.

** Course Policies ** Please see Course Policies for other details on tentative syllabus, evaluation and getting help.

Administrative Information

**Lectures:** Tuesday 4:00 pm - 6:50 pm.

Zoom link on Diderot. First meeting: **Sep 1**

**Listeners and Auditors are welcome. ** (Email Peter for zoom link).

**Office Hours:** Pravesh: Wed 3-4pm, Peter: Mon 2-3pm, also by appointment.

**Diderot**: Use Diderot to access interactive lecture notes, discussions and announcements.

**Evaluation:**
1. 4-6 **homeworks** (60 percent) - must be typeset and submitted every Tuesday (except HW0) through Gradescope

2. Expository **Lecture Notes ** (40 percent, done individually) - on a related topic

**Gradescope**
Sign up here (use your andrew ID to login please, and code MW86ZP if needed.)

** Resources **: Lecture notes and other references on Diderot.

A recent survey covering a subset of topics.

** Related Classes **:
SoS Seminar at Princeton/MIT

Moses Charikar's Class on Hierarchies at Stanford

Luca Trevisan's Spectral Methods at Berkeley

Tentative Schedule | |||

Lecture # | Topic | Notes | Homework |
---|---|---|---|

1. 09/01 | Introduction + Basics (SoS Proofs, Pseudo-Expectations, SDP Solving) | HW0 released (due 9/4) | |

2. 09/08 | Rounding Via Second Moments: Algorithms and Lower-bounds for Max-Cut | HW1 released (due 9/22) | |

3. 09/15 | RPR^2 Framework, Max 2SAT, Coloring 3-colorable Graphs | ||

4. 09/22 | Rounding Degree 4 SoS: Sparsest Cut | HW1 due, HW2 released (due 10/06) | |

5. 09/29 | TBD | ||

6. 10/06 | TBD | ||

7. 10/13 | TBD | ||

8. 10/20 | TBD | ||

9. 10/27 | TBD | ||

10. 11/03 | TBD | ||

11. 11/10 | TBD | ||

12. 11/17 | TBD | ||

13. 11/24 | TBD | ||

14. 12/01 | TBD | ||

15. 12/08 | TBD |