Completed
Streaming Algorithms
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Separations and Equivalences Between Turnstile Streaming and Linear Sketching
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Streaming Algorithms
- 3 Streaming Models
- 4 Limitations on Equivalence
- 5 Our Results
- 6 Linear Sketching
- 7 Reduction Requirements
- 8 Stream Conditions
- 9 Separating Turnstile Algorithms and Linear Sketches
- 10 Bounded-Degree Triangle Counting
- 11 Constant-Degree Triangle Counting
- 12 Insertion-Only Triangle Counting
- 13 Extending the Insertion-Only Algorithm
- 14 Separation
- 15 Constructivity
- 16 Conclusion and Further Work
