In this graduate seminar we cover recent research on the use of mathematical programming for problems arising from optimization, machine learning, computational complexity and more, with a particular focus on the Parrilo Lasserre “Sum of Squares” semidefinite programming hierarchy. We discuss both lower and upper bounds, as well as how such mathematical programs give rise to a general theory of computational difficulty, computation vs. sample size tradeoffs, and computational analogs of Bayesian probabilities.

See Princeton registrar for formal prerequisites. The seminar assumes the following skills:

- Mathematical maturity
- comfort with mathematical proofs, discrete structures (e.g., graphs), basic linear algebra (e.g., eigenvalues), basic probability theory (e.g., Chernoff bounds)
- Algorithmic thinking
- familiarity with mathematical models of computation (e.g., Turing machines), basic algorithms (e.g., dynamic programming, network flow)
- Optimization
- familiarity with the concept of convexity, mathematical programming, (e.g., linear programming, semidefinite programming) and basic optimization methods (e.g., gradient descent, simplex method, ellipsoid method)

We will have *weekly* homework assignments. We strongly encourage you to attempt to solve all of the assigned exercises. However, submission of your solutions is optional and the solutions will not be graded.

- Upper and lower bounds for various average case problems, including random constraint satisfaction, planted clique, and problems arising from machine learning such as tensor decomposition, sparse coding, and more.
- Speeding up the Sum-of-Squares algorithm to obtain practically efficient algorithms.
- Khot’s Unique Games Conjecture (UGC) and the SOS approach to refuting the UGC.
- Can SOS be optimal algorithm in some settings? What kind of implications could such optimality entail?
- Semidefinite extension complexity and connections to communication complexity.
- Connections of Sum-of-Squares:
- statistical physics, and algorithms such as belief propagation and survey propagation.
- Connections to quantum information theory, quantum entanglement, and the log rank conjecture.
- Connections to extremal combinatorics via Razborov’s flag algebras.