Cut Sparsification and Succinct Representation of Submodular Hypergraphs

Explore cut sparsification of hypergraphs in this 37-minute lecture by Robert Krauthgamer from the Weizmann Institute of Science. Delve into the generalization of cut sparsification to submodular hyperedges, examining new bounds and improvements for various submodular function families. Learn about the first polynomial bound for all submodular functions and investigate the common setting where the sparsifier is a reweighted sub-hypergraph. Discover a more general notion of succinct representation, measuring size in bits rather than hyperedge count. Gain insights into this research conducted in collaboration with Yotam Kenneth, presented as part of the Simons Institute's "Sublinear Graph Simplification" series.