Explore a 19-minute IEEE conference talk on hypergraph cut sparsifiers, presented by researchers from the University of Pennsylvania and University of Washington. Delve into the concept of near-linear size hypergraph cut sparsifiers, examining their applications in SAT sparsification and the challenges in achieving optimal size. Learn about edge strengths, cut counting bounds, and the limitations of existing approaches. Discover a modified approach that utilizes balance weight assignment to overcome previous obstacles. Gain insights into the remaining tasks and concluding remarks on this cutting-edge topic in graph theory and algorithm design.
Overview
Syllabus
Intro
Size of Cut Sparsifier
Hypergraph Cut Sparsifiers
Size of Hypergraph Sparsifier
An Application: SAT Sparsification
Edge Strengths
Cut Sparsifier for Hypergraphs KK15
Cut Counting Bound in Hypergraphs is Tight
An Example when [KK15] Gives Large Sparsifier
Two Examples
Our Approach
Works on Both Examples
Counter Example
A Modified Approach
Balance Weight Assignment
Remaining Tasks
Concluding Remarks
Taught by
IEEE FOCS: Foundations of Computer Science
