Succinct Graph Structures and Their Applications S2022

Lecture Time & Place: Thursday 10:15-12:00, Ziskind 155 
TA: Orr Fischer
Prerequisite: Sufficient comfort with graph algorithm design & analysis.

The home exam can be found here.

Typo in Ex. 5.  See correction here
Good luck!

Block 1: Distance Preserving Structures 

(31/03) 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)

(07/04) Lecture  02: Additive and Near-Additive Spanners LectureNotes-2018 Slides-2020
New Additive Spanners (Chechik, 2013)
(1+eps,1/eps) Spanners (Sec. 3.1 here

Exercise-1 Due May 03

(14/04) Lecture  03: Distance Oracles LectureNotes-2018 Slides-2020
Lecture 8 of Vassilevska Williams (CS 267, Graph Algorithms, Spring 2016)
Approximate Distance Oracles (Thorup and Zwick, 2005)

(21/04) Passover, No Class

(28/04) Holocaust Remembrance Day, No Class

(05/05) Independence Day, No Class

(12/05) Lecture  04: 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)

(19/05) Lecture  05: Labeling Schemes 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)

Exercise-2 Due June 02 (Sharp deadline)

(26/05) Lecture  06:  Probablistic Tree Embedding (FRT)  Slides 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)

Block 2: Cut Preserving Structures 

(02/06) HALG, No Class

(09/06) Lecture  07:  Cut Sparsifiers
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 2 of Bernhard Haeupler (Algorithmic Superpower Randomization, CMU,  Fall 2015)
Lecture 1 of Mohsen Ghaffari (Advanced Algorithms, ETH, Fall 2017)

Exercise-3 Due June 26 (Sharp deadline)

(16/06) Lecture  08:  Succinct Cut Representation (Gomory Hu) Lecture-08
Lecture 9 of Richard Peng (CS7510 Graph Algorithms, Georgia Institute of Technology, Fall 2019)
Lecture 6 of Chandra Chekuri (CS 598: Topics in Combinatorial Optimization, UIUC,  Fall 2010)

 

Block 3: Fault Tolerant Network Design

(23/06) STOC, No Class 

(30/06) Lecture  10: Fault Tolerant BFS Structures Slides-2018
Sparse Fault-Tolerant BFS Structures (Parter and Peleg, 2013)
Dual Failure Resilient BFS Structure (Parter, 2015)
Preserving Distances in Very Faulty Graphs (Bodwin, Grandoni, Parter. Vassilevska Williams, 2017)

(07/07) Lecture  11: Distance Sensitivity Oracles and Fault Tolerant Spanners Notes-2018
Oracles for Distances Avoiding a Failed Node or Link (Demetrescu, Thorup, Chowdhury, Ramachandran, 2008)
Fault-Tolerant Spanners for General Graphs (Chechik, Langberg, Peleg, Roditty 2009)
Fault-Tolerant Spanners: Better and Simpler (Dinitz, Krauthgamer, 2011)
Optimal Vertex Fault Tolerant Spanners (Bodwin, Dinitz, Parter, Williams, 2018)
A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners (Bodwin, Patel, 2019)