Lower Bounds for Maximal Matchings and Maximal Independent Sets

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.