Lower Bounds for Maximal Matchings and Maximal Independent Sets
Offered By: IEEE via YouTube
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
Cloud Computing Concepts, Part 1University of Illinois at Urbana-Champaign via Coursera Cloud Computing Concepts: Part 2
University of Illinois at Urbana-Champaign via Coursera Reliable Distributed Algorithms - Part 1
KTH Royal Institute of Technology via edX Introduction to Apache Spark and AWS
University of London International Programmes via Coursera Réalisez des calculs distribués sur des données massives
CentraleSupélec via OpenClassrooms