YoVDO

Distributed Lower Bounds for Ruling Sets

Offered By: IEEE via YouTube

Tags

IEEE FOCS: Foundations of Computer Science Courses Distributed Algorithms Courses

Course Description

Overview

Explore a comprehensive analysis of distributed lower bounds for ruling sets in this 22-minute IEEE conference talk. Delve into the state-of-the-art deterministic algorithms, examining the authors' novel results for both deterministic and randomized approaches. Gain insights into the Round Elimination technique and its application in deriving lower bounds. Investigate upper bounds for ruling sets, including problem families and color reduction concepts. Conclude with a discussion on open questions in the field, providing a thorough overview of current research in distributed computing and graph theory.

Syllabus

Intro
(2, 1)-ruling set = MIS
(a, b)-ruling set
State of the art (deterministic)
Our results (deterministic)
Our results (deterministic, on trees)
Our results (randomized)
Technique: Round Elimination
How we use Round Elimination
Upper bounds for ruling sets
Upper bound problem family: example
Upper bound sequence
Color reduction: big picture
From upper bound to lower bound
Open questions


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