Introduction to Convex Relaxations

Friday 
October 5 
Lecture 1

LP Duality

Monday 
October 8 
Lecture 2

DualityBased LP Rounding

Friday 
October 12 
Lecture 3

Randomized LP Rounding

Monday 
October 22 
Lecture 4

Heuristics for Solving Convex
Programs

Monday 
November 5 
See:
Section 2
Section
17.2.4
Extra
Homework 1
Solutions

Hoffman Circulation Theorem

Monday 
November 12 
Lecture 6

Algorithms for Asymmetric TSP

Monday 
November 19 
See:
This paper

Spectral Partitioning

Friday 
November 23 
Lecture 8
Based on Chapters 1 and 2 from
these notes by Luca Trevisan

Unique Games

Monday 
November 26 
See:
This paper

Unique Games Continued

Monday 
December 3 

Hashing and Dimension Reduction

Friday 
December 14 
See:
Section 1
Section 3
Sections 3 and 4

Streaming and Counting Distinct Elements

Monday 
December 17 
See:
These
notes
Homework 2
(Partial) Solutions

Final Exam 
Friday 
January 24 
