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.

• homework 1: due 9/26
• homework 2: due 10/10
• homework 3: due 10/31
• homework 4: due 11/14

Lecture notes and schedule

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

Lecture #	Date	Topic	Lecture notes
1	9/6	Randomized Min-Cut	Lecture 1
2	9/8	Hashing	Lecture 2
3	9/13	LP Duality	Lecture 3
4	9/15	LP Rounding	Lecture 4
5	9/20	Ellipsoid Algorithm	Lecture 5
6	9/22	Semi-Definite Programs	Lecture 6
7	9/27	Submodular Minimization	Lecture 7
8	9/29	Concentration Inequalities	Lecture 8
9	10/4	Streaming I	Lecture 9
10	10/6	Streaming II	Lecture 10
11	10/11	Johnson-Lindenstrauss	Lecture 11
12	10/13	Graph spanners	Lecture 12
	10/18	Fall Break
	10/20	Fall Break
13	10/25	Multiplicative Weights	Lecture 13
14	10/27	Online Algorithms	Lecture 14
15	11/1	Coding Theory	Lecture 15
16	11/3	Combinatorial Auctions	Lecture 16
17	11/8	Communication Complexity	Lecture 17
18	11/10	Computation of Nash	Lecture 18
19	11/15	Low-Rank Approximations and SVD	Lecture 19
20	11/17	Locality-Sensitive Hashing and Approximate Nearest Neighbors	Lecture 20
	11/22	Thanksgiving
	11/24	Thanksgiving
21	11/29	Data Structure Lower Bounds
22	12/1	Fine Grained Complexity
23	12/6	Differential Privacy
24	12/8	Smoothed Analysis