Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing
Offered By: IEEE via YouTube
Course Description
Overview
Explore a 23-minute IEEE conference talk on advanced graph algorithms, focusing on deterministic decremental reachability, strongly connected components (SCC), and shortest paths. Delve into the innovative approach using directed expanders and congestion balancing presented by researchers from Rutgers University, University of Copenhagen, and TTIC. Learn about the motivation behind this research, the concept of directed expanders, directed sparse cuts, decomposition techniques, and the lift operation. Gain insights into cutting-edge developments in graph theory and their applications to efficient algorithm design for dynamic graph problems.
Syllabus
Introduction
Strongly Connected Components
Motivation
Deterministic Decremental SCC
Directed Expanders
Directed sparse cuts
Decomposition
Lift
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against NatureIEEE 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