Quotient Sparsification for Submodular Functions

Explore a 29-minute lecture on quotient sparsification for submodular functions presented by Kent Quanrud from Purdue University at the Simons Institute. Delve into the unification of graph and hypergraph sparsification through a general theorem on sparsifying matroids and monotone submodular functions. Discover how this approach generalizes k-cuts in graphs and hypergraphs, and learn about its applications in preserving quotient weights in matroids, creating hypergraph cut sparsifiers, and reducing points in set systems while maintaining union weights. Examine algorithms for efficient sparsification of hypergraphs, set systems, and matroids in nearly linear time. Gain insights into this fresh perspective on optimization and algorithm design, which offers conceptual unity and practical applications in various areas of computer science and mathematics.

Quotient Sparsification for Submodular Functions