CS 698C/K: Applications of semidefinite programming in complexity theory

Course outline:

Semidefinite Programming has emerged as a great tool to solve problems in diverse areas such as combinatorial optimization and engineering. It is interesting as a class of problems because it is much more general than linear programming but not much harder to solve. Specially in Computer Science there has been lot of results using this tool. The course will have detailed introduction to the field of semidefinite programming and will cover various interesting applications like the best known approximation algorithm for max-cut (Goemans-Williamson) and the upper bound on Shannon Capacity.

Course notes

Date Topic Link
30th Dec 2013 Introduction to mathematical optimization Lecture 1
1st Jan 2014 Linear programming and convex optimization Lecture 2
6th Jan 2014 Convex sets Lecture 3
8th Jan 2014 Examples of convex sets Lecture 4
13th Jan 2014 Properties of convex sets Lecture 5
15th Jan 2014 Hyperplane separation theorems Lecture 6
20th Jan 2014 Dual cones Lecture 7
22th Jan 2014 Convex functions Lecture 8
27th Jan 2014 Matrices Lecture 9
29th Jan 2014 Spectral decomposition Lecture 10
3rd Feb 2014 Positive semidefinite matrix Lecture 11
5th Feb 2014 Positive semidefinite cone Lecture 12
10th Feb 2014 Semidefinite programming Lecture 13
12th Feb 2014 Examples of semidefinite programming Lecture 14
24th Feb 2014 Midsem solutions
26th Feb 2014 Duality theory Lecture 15
3rd March 2014 Strong duality Lecture 16
5th March 2014 Maximum cut Lecture 17
10th March 2014 Lovasz theta number Lecture 18
12th March 2014 Properties of Lovasz theta number Lecture 19
24th March 2014 Concentration inequalities Lecture 20



Linear Algebra

Functional Analysis