YoVDO

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

Offered By: Simons Institute via YouTube

Tags

Graph Theory Courses Combinatorics Courses Algorithms Courses Computational Complexity Courses Approximation Algorithms Courses Sublinear Algorithms Courses

Course Description

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

Related Courses

Approximation Algorithms Part I
École normale supérieure via Coursera Approximation Algorithms Part II
École normale supérieure via Coursera Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
Stanford University via Coursera Algorithm Design and Analysis
University of Pennsylvania via edX Delivery Problem
University of California, San Diego via Coursera