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

Boaz Barak and David Steurer

work in progress (Fall 2016)

Background (pdf version)

Notation (pdf version)


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)

A random graph with a hidden clique. The sum-of-squares algorithm maintains a set of beliefs about which vertices belong to the hidden clique. Despite learning no new information, as we invest more computation time, the algorithm reduces uncertainty in the beliefs by making them consistent with increasingly powerful proof systems. Initially the beliefs have maximum uncertainty and correspond to the uniform distribution but they eventually converge on the correct hidden clique (red edges).

Seminars & workshops