course description

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.

prerequisites

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)

homework

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.

tentative list of topics

  • 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.