6.851: Advanced Data Structures (Spring'14)
Prof. Erik Demaine TAs: Timothy Kaler, Aaron Sidford
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 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,