Completed
Upper bounds for ruling sets
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Distributed Lower Bounds for Ruling Sets
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 (2, 1)-ruling set = MIS
- 3 (a, b)-ruling set
- 4 State of the art (deterministic)
- 5 Our results (deterministic)
- 6 Our results (deterministic, on trees)
- 7 Our results (randomized)
- 8 Technique: Round Elimination
- 9 How we use Round Elimination
- 10 Upper bounds for ruling sets
- 11 Upper bound problem family: example
- 12 Upper bound sequence
- 13 Color reduction: big picture
- 14 From upper bound to lower bound
- 15 Open questions
