Sparsification: Graphs, CSPs and Codes - Sublinear Graph Simplification
Offered By: Simons Institute via YouTube
Course Description
Overview
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
Fundamentals of Electrical EngineeringRice University via Coursera Code-Based Cryptography
Inria (French Institute for Research in Computer Science and Automation) via France Université Numerique An Introduction to Coding Theory
Indian Institute of Technology Kanpur via Swayam Randomized Methods in Complexity
Indian Institute of Technology Kanpur via Swayam Introductory Concepts of Digital Computing
CEC via Swayam