YoVDO

Cut Sparsification and Succinct Representation of Submodular Hypergraphs

Offered By: Simons Institute via YouTube

Tags

Graph Theory Courses Data Structures Courses Theoretical Computer Science Courses Combinatorial Optimization Courses Approximation Algorithms Courses Hypergraphs Courses

Course Description

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
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 Dinur
Institute 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