6.851: Advanced Data Structures (Spring'14)

Prof. Erik Demaine TAs: Timothy Kaler, Aaron Sidford

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

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]

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.