Winter, 2018

** Students should consult this page at least once a week
for important information. **

ANNOUNCEMENT Dec 28. Welcome to the course! Announcements will be here.

** Lectures: ** Wednesday 3-5 Room BA 4010

** Instructor: ** Toniann Pitassi, email: toni@cs

Office: Sandford Fleming 2305A, 978-3695

Office Hours: by appointment

**
CLASS SCHEDULE AND NOTES
**

- Lecture 1: Intro
- Lecture 2: Sherali Adams
- Lecture 3: Sherali Adams, cont'd
- SOS basics
- SOS duality
- Maxcut
- Scheduling via SOS
- Grothendieck
- How to Round any CSP
- More Rounding
- Learning Gaussians 1a
- Learning Gaussians 1b
- Learning Gaussians 2
- Dictionary Learning via SOS
- 3XOR SOS Lower Bound
- Extended Formulations Lower Bounds

** HOMEWORK AND PRESENTATIONS **

** ALGORITHMS VIA SOS PAPERS **

- Outlier-Robust Estimation Via SOS [KS'17]
- Fast Spectral Alg from SOS proofs: Tensor Decomp and Planted Sparse Vectors [HSSS'16']
- The Power of SOS for Detecting Hidden Structures [HKPRSS'17]
- Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems [HS'17]
- Tensor Principle Component Analysis via SOS Proofs [HSS'15]
- Quantum Entanglement, SOS and the log rank conjecture [BKS'17]

** LOWER BOUNDS **

- Size-Width Tradeoff for Resolution [BW]
- Linear Lower Bounds for PC [BGIP'99]
- Linear SOS Lower Bounds [G'01]
- SOS lower bounds [S'08]
- Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs [KMR'16]
- Random CNFs are Hard for Cutting Planes [FPPR'17]
- Random Formulas, Monotone Circuits and Interpolation [HP'17]

** COURSES, SURVEY TALKS, NOTES **

- Rothvoss Survey article (an excellent read)
- Aaron Potechin seminar on SOS 2018
- Similar Course by Massimo Lauria
- Boaz Barak research blog, Intro to SOS
- Barak SOS Course
- Steurer/Kothari SOS Course
- ML Theory Course Princeton 2017
- Amazing blog by Sam Hopkins on using SOS for Algorithms
- Atserias Talk Semialgebraic Proof Systems
- Atserias Mini Tutorial 2014
- Razborov's Proof Complexity Course
- Notes from Razborov's Course

** PROOF COMPLEXITY SURVEYS **