Instructor: Matt Weinberg
TAs: Meryem Essaidi, Dingli Yu
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://us.edstem.org/courses/107/discussion/. Enroll using the enroll
code: https://us.edstem.org/join/JaXjsT.
Announcements
will be posted below:

Use the enroll code 521StudentFA19 to enroll in the course on MTA.
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 Mechanical TA here.
PS1 is now available here.
Submit to MTA by 9/30 at 11:59pm.
PS2 is now available here.
Submit to MTA by 10/14 at 11:59pm.
PS3 is now available here.
Submit to MTA by 11/4 at 11:59pm.
PS4 is now available here.
Submit to MTA by 11/18 at 11:59pm.
PS5 is now available here.
Submit to MTA by 12/9 at 11:59pm.
Final is now available here.
Follow submission instructions in the PDF.
Final Exam/Project Guidelines: here.
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/12 
Hashing 

9/17 
Randomized MinCut 

9/19 
Concentration Bounds 

9/24 
Hashing to Reals 

9/26 
LP Rounding 

10/1 
LP Duality 

10/3 
LP Rounding 

10/8 
Multiplicative Weights 

10/10 
JohnsonLindenstrauss 

10/15 
LocalitySensitive Hashing and Approximate Nearest
Neighbors 

10/17 
LowRank Approximations and SVD 

10/22 
Random Walks and Markov Chains (Guest Lecture:
Sahil Singla) 

10/24 
Counting and Sampling Problems (Guest Lecture:
Sahil Singla) 

10/29 
Fall Break 

10/31 
Fall Break 

11/5 
SemiDefinite Programs 

11/7 
Ellipsoid Algorithm 

11/12 
Submodular Minimization 

11/14 
Computation of Nash 

11/19 
Combinatorial Auctions I 

11/21 
Combinatorial Auctions II 

11/26 
Communication Complexity 

11/28 
Thanksgiving 

12/3 
Online Algorithms 

12/5 
Differential Privacy 

12/10 
Coding Theory 

12/12 
TBA 
TBA 