YoVDO

Sparsification: Graphs, CSPs and Codes - Sublinear Graph Simplification

Offered By: Simons Institute via YouTube

Tags

Graph Theory Courses Error-Correcting Codes Courses Constraint Satisfaction Problems Courses Hypergraphs Courses

Course Description

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
Explore the concept of sparsification in graphs, constraint satisfaction problems (CSPs), and codes in this 49-minute lecture by Madhu Sudan from Harvard University. Delve into the history of graph sparsification, starting with the seminal works of Karger and Benczur in the 1990s. Examine how graphs can be compressed to nearly linear size while preserving cut information. Investigate the broader notion of structure sparsification with respect to query classes. Learn about CSP sparsification as proposed by Kogan and Krauthgamer in 2015, which unifies various sparsification problems. Discover the introduction of code sparsification as a new class of problems, abstracting techniques from graph sparsification. Explore how this generalization resolves questions in CSP sparsification and leads to a complete classification of symmetric Boolean CSPs allowing nearly linear sized sparsification. Gain insights into the latest developments in this field, including joint work with Sanjeev Khanna and Aaron Putterman.

Syllabus

Sparsification: Graphs, CSPs and Codes


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