YoVDO

Lower Bounds for Maximal Matchings and Maximal Independent Sets

Offered By: IEEE via YouTube

Tags

IEEE FOCS: Foundations of Computer Science Courses Graph Theory Courses Distributed Computing Courses

Course Description

Overview

Explore the fundamental concepts of maximal matchings and maximal independent sets in graph theory through this 24-minute IEEE conference talk. Delve into the distributed setting using the LOCAL model, and gain insights into lower bounds for these classical graph problems. Follow along as the speakers present a proof sketch, introduce the round elimination technique, and discuss the main lemma. Examine the lower bound for the LOCAL model and conclude with open problems in this field, providing a comprehensive overview of current research in distributed graph algorithms.

Syllabus

Intro
Two classical graph problems
Distributed setting (LOCAL model)
Simple scenario
Proof sketch
Round elimination technique
Main Lemma
Lower bound for the LOCAL model
Conclusions and open problems


Taught by

IEEE FOCS: Foundations of Computer Science

Tags

Related Courses

An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature
IEEE via YouTube
Computation in the Brain Tutorial - Part 2
IEEE via YouTube
Computation in the Brain - Part 1
IEEE via YouTube
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
IEEE via YouTube
Cookbook Lower Bounds for Statistical Inference in Distributed and Constrained Settings - Part 1
IEEE via YouTube