Instructors: Mark
Braverman, Matt
Weinberg
TAs: Linda Cai, Zhou Lu
For contact information, course description,
collaboration/grading policy, etc., please see the course infosheet.
Ed: We will use Ed for course
discussion. The link is: https://edstem.org/us/courses/8773/discussion/. If you are enrolled in the
course, you should have access to Ed. Please email the instructors if you
cannot access Ed.
codePost: Course assignments will be submitted to codePost.
You can enroll in the course using this link (must use
an @princeton or @cs.princeton email address).
Announcements
will be posted below:

Guidelines for the final
exam/project are posted: final
guidelines.

The final exam is now
posted: final exam.
Homework: Homeworks will be posted
below when they become available. Here
is a LaTeX template you may use for the homework, and here
is a short guide to LaTeX. Feel free to visit office hours for help
installing/setting up LaTeX. Submit your homework through codePost here.
Lecture Notes:
We will use
lecture notes from previous iterations, and mostly follow the same schedule.
Below is a tentative schedule:
Date 
Topic 
Reading
Material 
9/2 
Randomized MinCut 

9/7 
LP Rounding I 

9/9 
LP Rounding II 

9/14 
LP Duality 

9/16 
SemiDefinite Programs 

9/21 
Hashing 

9/23 
Concentration Inequalities 

9/28 
Martingales 
See Ed 
9/30 
Random Walks and Markov Chains 

10/5 
Multiplicative Weights 

10/7 
JohnsonLindenstrauss 

10/12 
LocalitySensitive Hashing and Approximate Nearest
Neighbors 

10/14 
LowRank Approximations and SVD 

10/19 
Fall Break 

10/21 
Fall Break 

10/26 
Coding Theory 

10/28 
Online Algorithms I 

11/2 
Online Algorithms II 

11/4 
Computation of Nash 

11/9 
Ellipsoid Algorithm 

11/11 
Submodular Minimization 

11/16 
Communication Complexity 

11/18 
Hashing to Reals 

11/23 
Differential Privacy 

11/25 
Thanksgiving Break 

11/30 
Combinatorial Auctions I 

12/2 
Combinatorial Auctions II 