Instructor Matt Weinberg, Huacheng Yu
Lectures Tuesday/Thursday 1:30-2:50pm
TAs Kaifeng Lyu, Haoyu Zhao
Location Thomas Lab 003
Office hours Huacheng: Tue 3:00-4:00pm @ CS310
Haoyu: Wed 2:00-4:00pm @ CS413
Matt: Thu 3:00-4:00pm @ CS317
Kaifeng: Fri 4:00-6:00pm @ CS413

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/28064/discussion/. If you are enrolled in the course, you should have access to Ed. Please email the instructors if you cannot access Ed.

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.

Lecture notes and schedule

For most lectures, we will use lecture notes from previous iterations. Below is a tentative schedule.

Lecture #DateTopicLecture notes
19/6Randomized Min-CutLecture 1
29/8HashingLecture 2
39/13LP DualityLecture 3
49/15LP RoundingLecture 4
59/20Ellipsoid AlgorithmLecture 5
69/22Semi-Definite ProgramsLecture 6
79/27Submodular MinimizationLecture 7
89/29Concentration InequalitiesLecture 8
910/4Streaming ILecture 9
1010/6Streaming IILecture 10
1110/11Johnson-LindenstraussLecture 11
1210/13Graph spannersLecture 12
10/18Fall Break
10/20Fall Break
1310/25Multiplicative WeightsLecture 13
1410/27Online AlgorithmsLecture 14
1511/1Coding TheoryLecture 15
1611/3Combinatorial AuctionsLecture 16
1711/8Communication ComplexityLecture 17
1811/10Computation of NashLecture 18
1911/15Low-Rank Approximations and SVDLecture 19
2011/17Locality-Sensitive Hashing and Approximate Nearest NeighborsLecture 20
11/22Thanksgiving
11/24Thanksgiving
2111/29Data Structure Lower Bounds
2212/1Fine Grained Complexity
2312/6Differential Privacy
2412/8Smoothed Analysis