Lecture Time & Place: Thursday 10:15-12:00, Ziskind 155 Zoom link
TA: Avi Cohen
Prerequisite: Sufficient comfort with both algorithm design & analysis.
Home Exam (due midnight of Aug. 5)
Course Schedule:
(23/04) Lecture 01: Graph Spanners, Greedy Construction, Girth Conjecture, and
3-spanner Algorithm by Baswana-Sen. Slides Notes-2018 Exercise-01 due May 27
- 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)
(30/04) Lecture 02: Additive and Nearly-Additive Spanners. Slides Notes-2018
- New Additive Spanners (Chechik, 2013)
- The 4/3 Additive Spanner Exponent is Tight (Abboud and Bodwin, 2016)
- (1+eps,1/eps) Spanners (Sec. 3.1 here)
- Elkin-Peleg's construction
(07/05) Lecture 03: Distance Oracles. Slides Notes-2018
- Lecture 8 of Vassilevska Williams (CS 267, Graph Algorithms, Spring 2016)
- Approximate Distance Oracles (Thorup and Zwick, 2005)
(14/05) Lecture 04: Routing Schemes. Slides 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)
(21/05) Lecture 05: Labeling Schemes. Slides 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)
(28/05) No Class (Shavuot) Exercise-02 due June 14
(04/06) 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)
(11/06) Lecture 07: Cut Sparsifiers Slides Notes-2018 Exercise-03 due June 28
- 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)
(18/06) Lecture 08: Efficienct Min-Cut Computation Slides
- Minimum Cuts in Near-Linear Time (Karger, 96)
- Section A.1 of Random Sampling in Cut, Flow, and Network Design Problems (Karger, 99)
(25/06) Lecture 9: Succinct Cut Representation (Gomory Hu) Slides
- 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)
(02/07) Lecture 10: Fault-Tolerant Graph Structure I: FT-BFS Structures
Notes-'20 Slides-'13 Exercise-04 due July 16
- 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)
(09/07) No Class (Seventeenth of Tammuz Fast)
(16/07) Lecture 11: Fault-Tolerant Graph Structure II: Distance Sensitivity Oracles and Fault Tolerant Spanners. Notes-2018 Notes-2020
- 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)
Useful Probabilities Inequalities: Handout by Avrim Blum and Anupam Gupta (15-859 Randomized Algorithms, CMU, Spring'11).