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."
Homework 1: due Monday
10/9 at 11:59pm.
Homework 2: due
Thursday 11/9 at 11:59pm.
Homework 3: due Monday
11/27 at 11:59pm.
Homework 4: due Monday
12/18 at 11:59pm.
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 
