YoVDO

Maximal Matching in Bounded-deletion Streams

Offered By: Simons Institute via YouTube

Tags

Graph Theory Courses Data Structures Courses Algorithm Analysis Courses Computational Complexity Courses Space Complexity Courses Sublinear Algorithms Courses

Course Description

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
Explore the intricacies of maximal matching in bounded-deletion graph streams through this 38-minute lecture by Christian Konrad from the University of Bristol, UK. Delve into the study of graphs revealed as sequences of edge insertions and deletions, with a focus on scenarios where deletions are limited to a parameter K. Examine the single-pass streaming space complexity of this problem, known to be Θ(n^2) for unrestricted K, where n represents the number of vertices. Discover a new algorithm and matching lower bound result that provide a comprehensive understanding of how space complexity evolves as a function of K. Gain insights into sublinear graph simplification techniques and their applications in this Simons Institute presentation.

Syllabus

Maximal Matching in Bounded-deletion Streams


Taught by

Simons Institute

Related Courses

Sampling-Based Sublinear Low-Rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning
Association for Computing Machinery (ACM) via YouTube
Sublinear Algorithms for Gap Edit Distance
IEEE via YouTube
High Dimensional Robust Sparse Regression
Simons Institute via YouTube
Learning-Augmented Sketches for Frequency Estimation
Simons Institute via YouTube
Adaptive Sparse Recovery with Limited Adaptivity
Simons Institute via YouTube