Lecture Time & Place: Wednesday 11:00-12:30, Ziskind 155
TA: Yinon Nahum
Prerequisite: Sufficient comfort with both algorithm design & analysis.
Course Schedule:
- (28/03) Lecture 01: Graph Spanners, Greedy Construction, Girth Conjecture, and
3-spanner Algorithm by Baswana-Sen. Lecture 01, Exercise 01 , Solution for 2b- 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)
- (11/04) Lecture 02: Distance Oracles. Lecture 02 Exercise 02
- Lecture 8 of Vassilevska Williams (CS 267, Graph Algorithms, Spring 2016)
- Approximate Distance Oracles (Thorup and Zwick, 2005)
- (18/04) No Class due to Memorial Day
- (25/04) Lecture 03: Routing Schemes. Lecture 03
Note: This lecture is heavily built upon previous lecture, try to recap before class.- 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)
-
(02/05) Lecture 04: Labeling Schemes. Lecture 04 Exercise 03
- 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)
- (09/05) Lecture 05: Probabilistic Tool-Kit (Guest Session by Yinon). Lecture 05
- (16/05) Lecture 06: Low Diameter Decomposition and Tree Embedding . Lecture 06
- 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)
- (23/05) Lecture 07: Embedding into Sub-Trees. Lecture 07 Exercise 04 Sol 04
- Lower-Stretch Spanning Trees (Elkin, Emek, Spielman and Teng, 2008)
- Improved Embeddings of Graph Metrics into Random Trees (Dhamdhere, Gupta, R¨acke, 2006).
- Notes of Michel X. Goemans (Topics in TCS, MIT, 2006)
- (30/05) Lecture 08: Cut Sparsifiers. Lecture 08
- 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)
- (06/06) Lecture 09: Additive Spanners. Lecture 09
- Fast Estimation of Diameter and Shortest Paths (Aingworth, Chekuri, Indyk, Motwani 1999)
- New Additive Spanners (Chechik, 2013)
- The 4/3 Additive Spanner Exponent is Tight (Abboud and Bodwin, 2016)
- (13/06) No Class
- (20/06) Lecture 10: Fault Tolerant Network Design I, FT-BFS Structures. Lecture 10 (Slides)
- Sparse Fault-Tolerant BFS Structures (Parter and Peleg, 2013)
- Sparse Fault-Tolerant BFS Structures (Parter and Peleg, 2013)
- (27/06) Lecture 11: Fault Tolerant Network Design II, Distance Sensitivity Oracles and Fault Tolerant Spanners. Lecture 11
- 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)
- (04/07) Lecture 12: Approximate Shortest Paths. Lecture 12
- All-pairs almost shortest paths (Dor, Halperin, Zwick, 2000)
- All-pairs almost shortest paths (Dor, Halperin, Zwick, 2000)
Useful Probabilities Inequalities: Handout by Avrim Blum and Anupam Gupta (15-859 Randomized Algorithms, CMU, Spring'11).