Proofs, beliefs, and algorithms through the lens of sum-of-squares

Lectures

1.1. Introduction (pdf version) (video)

1.2. Sum-of-squares over the hypercube (pdf version) (video)

2.1. Max Cut (pdf version) (video)

2.2. Cheeger (pdf version) (video)

2.3. Grothendieck (pdf version) (video)

3.1. Lower bounds—Max Cut (pdf version) (video)

3.2. Lower bounds—CSP (pdf version) (video)

3.3. Lower bounds—Unique Games Conjecture (pdf version) (video)

4.1. Arora–Rao–Vazirani Approximation for Sparsest Cut (pdf version) (video)

5.1. The Bayesian view of pseudo distributions (pdf version) (video)

5.2. Sum-of-squares over general domains (pdf version)

5.3. Lower bounds—Planted Clique (pdf version) (video)

5.6. Lower Bounds—Knapsack (pdf version)

6.1 Flag algebras and extremal combinatorics. (pdf version) (video)

7.1. SOS and the unit sphere—Sparse vectors, tensor decomposition, dictionary learning, and quantum separability (pdf version) (video)

7.2. Finding a sparse vector in a subspace (pdf version) (video)

7.4. Tensor decomposition via sum of squares (pdf version) (video)

7.5. Dictionary learning via tensor decomposition (pdf version)

8.1. Quantum entanglement, log rank conjecture, and sum of squares (pdf version) (video)

9.1. SOS and the Unique Games conjecture—a love hate relationship (pdf version) (video)

9.2. The small set expansion hypothesis (pdf version) (video)

9.4. On approaches for proving the Unique Games Conjecture (pdf version) (video)

10.1 Is sos an “optimal algorithm”? (pdf version) (video)

10.2 Digression to boosting, experts, dense models, and their quantum counterparts (pdf version) (video)

10.3 Optimality of sos among similar sized sdp’s for csp’s (pdf version) (video)