Instructor	Huacheng Yu
Lectures	Monday/Wednesday 3:00-4:20pm
TAs	Haichen Dong
Location	Friend Center 008
Office hours	Huacheng: M/W after lecture @ CS310 or by appointment Haichen Dong: TBD

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 instructor if you cannot access Ed.

Homework

There are four homeworks. In each homework, you will submit an "interesting observation" related to any paper we discussed (or about graph algorithms in general). The deadlines are Sep 30, Oct 28, Nov 18, Dec 9. You may skip one of the homeworks with no penalty.

Lecture notes and schedule

Below is a tentative schedule.

Lecture #	Date	Topic	Lecture notes	Presenter
1	9/4	Negative-Weight Single-Source Shortest Paths in Near-linear Time	Notes 1	Huacheng Yu
2	9/9		Notes 2
3	9/11	Preliminaries on expander graphs, max flow algorithms	Notes 3	Huacheng Yu
4	9/16	The Expander Hierarchy and its Applications to Dynamic Graph Algorithms	Notes 4	Huacheng Yu
5	9/18		Notes 5
6	9/23	Maximum Flow by Augmenting Paths in n^{2+o(1)} Time		Huacheng Yu
7	9/25
8	9/30	Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time		Huacheng Yu
9	10/2
10	10/7	Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time		Ilya Maier Ijay Narang Baris Onat
11	10/9
	10/14	Fall break
	10/16	Fall break
12	10/21	Distributed MST and Routing in Almost Mixing Time		Hareton Song Chen Zhang Chengyuan Deng
13	10/23
14	10/28	Towards a Unified Theory of Sparsification for Matching Problems Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds		Zhijun Zhang Adithya Bhaskar
15	10/30
16	11/4	Dynamic Algorithms for Maximum Matching Size Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time		Pachara Sawettamalya Elena Gribelyuk Akhil Jakatdar
17	11/6
18	11/11	Dynamic (1+ε)-Approximate Matching Size in Truly Sublinear Update Time		Huacheng Yu
19	11/13
20	11/18	Deterministic Near-Linear Time Minimum Cut in Weighted Graphs		Frederick Qiu Chenxiao Tian Jessica Choe
21	11/20
22	11/25	Cactus Representation of Minimum Cuts: Derandomize and Speed up		Zhongtian He
	11/27	Thanksgiving break
23	12/2	Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time		Huacheng Yu
24	12/4