Semidefinite Programming and Constraint Satisfaction

Summer 2014 REU

Instructors: Yury Makarychev and Madhur Tulsiani


Schedule (6/24-7/11)
Lectures: MTF 2:15-3:45, TTIC 530

The course will cover the following topics:

  • Introduction to Constraint Satisfaction Problems (CSPs) and approximation.
  • Applications of Semidefinite Programs (SDPs) for approximation: Max-Cut, Grothendieck problems, all CSPs.
  • Fast algorithms for approximately solving SDPs: the Arora-Kale framework.
  • SDPs for approximating the maximum of polynomials over semialgebraic sets: the Sum-of-Squares hierarchy.



  • 6/24: Approximation algorithms for Max-Cut. Introduction to semidefinite programming.
  • 6/27: Semidefinite relaxation and Krivine's rounding scheme for the Grothendieck problem.
  • 6/30: Variants of the Grothendieck problem. Introduction to constraint satisfaction problems (CSPs) and approximation resistance. Approximation algorithm for all Boolean CSPs.
  • 7/1: The multiplicative weights update method and its application to solving LPs.
  • 7/7: Solving LPs and SDPs using multiplicative weights. Designing oracles for Set-Cover and Max-Cut.
  • 7/8: Analyzing the oracle for Max-Cut. Dual of an SDP and matrix version of the multiplicative weights update algorithm. Introduction to the Lasserre/Sum-Of-Squares hierarchy.
  • 7/11: The sum-of-squares proof system and it's connection to semidefinite programming hierarchies. Lower bound for 3-XOR.