Near-Linear Size Hypergraph Cut Sparsifiers

Near-Linear Size Hypergraph Cut Sparsifiers

IEEE FOCS: Foundations of Computer Science via YouTube Direct link

Intro

1 of 17

1 of 17

Intro

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. 1 Intro
  2. 2 Size of Cut Sparsifier
  3. 3 Hypergraph Cut Sparsifiers
  4. 4 Size of Hypergraph Sparsifier
  5. 5 An Application: SAT Sparsification
  6. 6 Edge Strengths
  7. 7 Cut Sparsifier for Hypergraphs KK15
  8. 8 Cut Counting Bound in Hypergraphs is Tight
  9. 9 An Example when [KK15] Gives Large Sparsifier
  10. 10 Two Examples
  11. 11 Our Approach
  12. 12 Works on Both Examples
  13. 13 Counter Example
  14. 14 A Modified Approach
  15. 15 Balance Weight Assignment
  16. 16 Remaining Tasks
  17. 17 Concluding Remarks

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.