Instructor	Huacheng Yu
Lectures	Monday/Wednesday 1:30-2:50pm
TAs	Elena Gribelyuk, Zhongtian He, Pachara (Akin) Sawettamalya, and Dwaipayan (Dwip) Saha
Location	Thomas Lab 003
Office hours	Huacheng: M/W 3-4pm @ CS310 Dwip: M 4:30-5:30pm, T 3-4pm @ CS 3rd floor Zhongtian: Th 3-5pm @ CS 3rd floor Akin: F 10am-noon @ CS 3rd floor Elena: F 4-6pm @ CS 3rd floor

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/46246/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. Please submit your solutions to Gradescope: https://www.gradescope.com/courses/605977.

• homework 1: due 9/24
• homework 2: due 10/8
• homework 3: due 10/29
• homework 4: due 11/19

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/11	Hashing	Lecture 2
3	9/13	LP Duality	Lecture 3
4	9/18	LP Rounding	Lecture 4
5	9/20	Ellipsoid Algorithm	Lecture 5
6	9/25	Semi-Definite Programs	Lecture 6
7	9/27	Submodular Minimization	Lecture 7
8	10/2	Concentration Inequalities	Lecture 8
9	10/4	Streaming I	Lecture 9
	10/9	Cancelled
	10/11	Cancelled
	10/16	Fall Break
	10/18	Fall Break
10	10/23	Streaming II	Lecture 10
11	10/25	Johnson-Lindenstrauss	Lecture 11
12	10/30	Low-Rank Approximations and SVD	Lecture 12
13	11/1	Locality-Sensitive Hashing and Approximate Nearest Neighbors	Lecture 13
14	11/6	Multiplicative Weights	Lecture 14
15	11/8	Online Algorithms	Lecture 15
16	11/13	Graph Spanners	Lecture 16
17	11/15	Distance Oracles	Lecture 17
18	11/20	Parameterized Complexity	Lecture 18
	11/22	Thanksgiving
19	11/27	Combinatorial Auctions	Lecture 19
20	11/29	Communication Complexity	Lecture 20
21	12/4	Coding Theory	Lecture 21
22	12/6	Fine Grained Complexity