Lecture Time & Place: Wednesday 10:15-12:00, Ziskind 155
TA: Orr Fischer
Prerequisite: Sufficient comfort with graph algorithm design and randomized algorithms
Block 1: Distance Preserving Structures
(17/04) Lecture 01: Graph Spanners, Greedy Construction, Girth Conjecture, and the Baswana-Sen Algorithm LectuteNotes-2018 Slides-2020
Lectures 6 and 7 of Vassilevska Williams (CS 267, Graph Algorithms, Spring 2016)
Section 2 in A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs (Baswana and Sen, 2007)
(01/05) Lecture 02: Distance Oracles LectureNotes-2018 Slides-2020
Lecture 8 of Vassilevska Williams (CS 267, Graph Algorithms, Spring 2016)
Approximate Distance Oracles (Thorup and Zwick, 2005)
Exercise-01 due to May 15
(08/05) Lecture 03: Routing Schemes
(15/05) Lecture 04: Labeling Schemes
(22/05) Lecture 05: Probablistic Tree Embedding (FRT)
Block 2: Cut Preserving Structures
(30/05) Lecture 06: Cut Sparsifiers
(05/06) Lecture 07: Succinct Cut Representation (Gomory Hu)
(12/06): No class (Shavuot)
Block 3: Reachability
(19/06) Lecture 08: Reachability Shortcuts
(03/07) Lecture 09: Hopsets
Block 4: Fault Tolerant Network Design
(03/07) Lecture 10: Fault Tolerant BFS Structures
(10/07) Lecture 11: Distance Sensitivity Oracles and Fault Tolerant Spanners