Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs

Simons Institute via YouTube

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
Explore a lecture on improved bounds for fully dynamic matching algorithms using Ordered Ruzsa-Szemeredi (ORS) Graphs. Delve into Sepehr Assadi's research, which builds upon the breakthrough work of Behnezhad and Ghafari. Examine the concept of ORS Graphs and their role in parameterizing algorithm runtimes for maximum matching problems. Learn about the improvements made to the BG-algorithm, reducing update time to n^{o(1)} * ORS(n). Understand how this advancement potentially simplifies dynamic matching algorithms to a purely combinatorial problem of upper bounding ORS(n). Gain insights into the current understanding of ORS(n) and its implications for algorithm efficiency in sublinear graph simplification.

Syllabus

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs

Taught by

Simons Institute

Reviews

Start your review of Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.