Cut Sparsification and Succinct Representation of Submodular Hypergraphs
Offered By: Simons Institute via YouTube
Course Description
Overview
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.
Syllabus
Cut Sparsification and Succinct Representation of Submodular Hypergraphs
Taught by
Simons Institute
Related Courses
Introduction to High Dimensional Expanders - Irit DinurInstitute for Advanced Study via YouTube The Average-Case Complexity of Counting Cliques in Erdos-Renyi Hypergraphs
IEEE via YouTube Graph Representation Learning and Its Applications to Biomedicine
Applied Algebraic Topology Network via YouTube Asaf Shapira - Local vs Global Combinatorics
International Mathematical Union via YouTube Tropical Solutions to Hard Problems in Auction Theory and Neural Networks - Lecture II
Hausdorff Center for Mathematics via YouTube