6.851: Advanced Data Structures (Spring'14)

Prof. Erik Demaine     TAs: Timothy Kaler, Aaron Sidford

[Home] [Lectures] [Assignments] [Project] [Open Problems] [Piazza]

Class 11 Video     [previous] [next] [completion form]

[+] Dynamic graph upper bounds (L19 + L20)

There weren't any questions about the two dynamic-graphs lectures, but there are lots of relatively new results on dynamic graphs, so I'll survey some of the coolest of them:

  • worst-case dynamic connectivity: polylogarithmic! (with high probability)
  • transitive closure: decent lower bounds (via 3SUM)
  • single-source reachability: connection to fast Boolean matrix multiplication, sublinear update for decremental
  • single-source path counting: strong lower bounds (assuming strong exponential time hypothesis!)
  • single-source shortest paths: lower bound via all-pairs shortest paths
  • sublinear decremental (1 + ε)-approximations
  • distance oracles: (1 + ε)-approximate shortest paths in static graphs
[The video still needs to be recorded or encoded. Stay tuned!]

Lecture notes, page 1/4[previous page][next page][PDF]

Lecture notes, page 1/4[previous page][next page][PDF]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email Erik.