15-859(E): Linear and Semidefinite Programming
(Advanced Algorithms) Fall 2011

Lecturers: Anupam Gupta and Ryan O'Donnell

Time: TR 12:00-1:20, GHC 4303
Course Blog: http://lpsdp.wordpress.com/

Office Hours: by appointment


      Homework 1 (due Thursday, September 22) and exercises (solutions)
      Homework 2 (due Thursday, September 29) and exercises (solutions)
      Homework 3 (due Tuesday, October 11) (solutions)
      Homework 4 (due Thursday, October 20)
      Homework 5 (due Thursday Tuesday, November 15)
      Homework 6 (due Tuesday, December 6)

(Solutions accessible only from CMU/Pitt.)

Scribe notes:

How to scribe

Course Description:

Linear Programs (LPs) and Semidefinite Programs (SDPs) are central tools in the design and analysis of algorithms. In this course, we will study the mathematical foundations behind these convex programs, give algorithms to solve them, and show how LPs and SDPs can be used to solve other algorithmic and math problems of interest. Here are some topics that we plan to cover in the course: Evaluation criteria: The course will have 6--7 homeworks; most problems will involve writing proofs, though some may involve rudimentary programming and working with LP/SDP solvers. Students will be required to act as scribes for the lectures. The breakdown is 75% homeworks, 15% scribing, 10% participation.

Background: We are looking for familiarity with a strong background in algorithms (at least 15-451 or equivalent), as well as significant mathematical maturity. If you do not have any background with LPs it would help to learn a bit about them before the class begins; one recommendation is the book Understanding and Using Linear Programming by Matoušek and Gärtner.

Maintained by Anupam Gupta and Ryan O'Donnell