Completed
Cut Counting Bound in Hypergraphs is Tight
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Near-Linear Size Hypergraph Cut Sparsifiers
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Size of Cut Sparsifier
- 3 Hypergraph Cut Sparsifiers
- 4 Size of Hypergraph Sparsifier
- 5 An Application: SAT Sparsification
- 6 Edge Strengths
- 7 Cut Sparsifier for Hypergraphs KK15
- 8 Cut Counting Bound in Hypergraphs is Tight
- 9 An Example when [KK15] Gives Large Sparsifier
- 10 Two Examples
- 11 Our Approach
- 12 Works on Both Examples
- 13 Counter Example
- 14 A Modified Approach
- 15 Balance Weight Assignment
- 16 Remaining Tasks
- 17 Concluding Remarks
