Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Cut Sparsification and Succinct Representation of Submodular Hypergraphs

Simons Institute via YouTube

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

Reviews

Start your review of Cut Sparsification and Succinct Representation of Submodular Hypergraphs

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.