Instructor: Matt Weinberg
TA: Divyarthi Mohan
For contact information, course description,
collaboration/grading policy, etc., please see the course infosheet.
Piazza: https://piazza.com/class/j7dw724yuexg7
Announcements
will be posted below:
Project Guidelines: initial proposal due 11/30 (optional).
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. To submit your homework, email it to Divya at dm23 (at) cs (dot)
Princeton (dot) edu by the deadline with subject line
"COS 521 HW X."
Lecture Notes:
We will use
lecture notes from previous iterations, and mostly follow the same schedule.
You can get a headstart on the lecture notes here (along with optional deeper reading material), and
notes will be posted below as the schedule becomes finalized.
Date 
Topic 
Reading
Material 
9/14 
Hashing 

9/19 
Randomized MinCut 

9/21 
Concentration Bounds 

9/26 
Hashing to Reals 

9/28 
Linear Programs 

10/3 
LP Rounding 
Lecture Notes 6 (slightly
different from last year) 
10/5 
LP Duality 
Lecture Notes 7 (different
from last year) 
10/10 
Decisions under Uncertainty 

10/12 
Learning from Experts 

10/17 
Dimensionality Reduction 

10/19 
Markov Chains 

10/24 
LowRank Approximations 

10/26 
SVD and Stochastic Block Model 

10/31 
Fall Break 

11/2 
Fall Break 

11/7 
Semidefinite Progamming 

11/9 
Ellipsoid Algorithm 
Lecture Notes 15 (slightly
different from last year) 
11/14 
Submodular Minimization 

11/16 
Game Theory: Equilibria 
Lecture Notes 17 (slightly
different from last year) 
11/21 
Combinatorial Auctions I 

11/23 
Thanksgiving 

11/28 
Combinatorial Auctions II 

11/30 
Communication Complexity 

12/5 
Gradient Descent (Guest Lecture: Sanjeev Arora) 

12/7 
Differential Privacy (Guest Lecture: Mark Bun) 

12/12 
Coding Theory 

12/14 
Online Algorithms 