Succinct Graph Structures and Their Applications S2018

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)
     
• (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)
     

Useful Probabilities Inequalities: Handout by Avrim Blum and Anupam Gupta (15-859 Randomized Algorithms, CMU, Spring'11).