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 Slides-2020 Notes-2018
Compact Routing Schemes (Thorup and Zwick, 2001)
A Data Structure for Dynamic Trees (Sleator and Tarjan, 1983)
Lecture 9 and Lecture 10 of Vassilevska Williams (CS 267, Graph Algorithms, Spring 2016)
(15/05) Lecture 04: Labeling Schemes (Presented by Asaf Petruschka) Asaf's Notes Slides-2020 Notes-2018
Chapter 19 in Peleg's book
Implicit Representation of Graphs (Kannan, Naor, Rudich, 1988)
Informative Labeling Schemes for Graphs (Peleg, 2005)
Distance Labeling in Graphs (Gavoille, Peleg, Pérennes and Raz, 2002)
Labeling Schemes for Flow and Connectivity (Katz, Katz, Korman, Peleg, 2002)
(22/05) Lecture 05: Probablistic Tree Embedding (FRT) Slides-2020 Notes-2018
On Approximating Arbitrary Metrices by Tree Metrices (Bartal, 1998)
A tight bound on approximating arbitrary metrics by tree metrics (Fakcharoenphol, Rao, Talwar, 2003)
Section 8.5 in the book "The design of approximation algorithms" by Williamson and Shmoys.
Lecture 7 of Mohsen Ghaffari (Advanced Algorithms, ETH, Fall 2017)
Exercise-02 due to June 10
Block 2: Cut Preserving Structures, Reachability
(30/05) Lecture 06: Cut Sparsifiers Notes-2018 Slides
Random sampling in cut, flow, and network design problems (Karger, 1994)
Randomized Approximation Schemes for Cut and Flows in Capacitated Graphs (Benczur and Karger, 2013)
Lecture 1 of Mohsen Ghaffari (Advanced Algorithms, ETH, Fall 2017)
(19/06) Lecture 07: Reachability Shortcuts Slides
SODA-2022 Paper
(26/06) Lecture 08: Succinct Cut Representation (Gomory Hu) Slides
CMPUT 675: Topics in Combinatorics and Optimization
Exercise-03 due to July 11
Block 4: Fault Tolerant Network Design
(03/07) Lecture 9: Fault Tolerant BFS Structures Slides-2013 Notes-2020
Sparse Fault-Tolerant BFS Structures (Parter and Peleg, 2013)
(10/07) Lecture 10: Distance Sensitivity Oracles and Fault Tolerant Spanners