A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond
Offered By: IEEE via YouTube
Course Description
Overview
Explore a 26-minute IEEE conference talk on a deterministic algorithm for balanced cut and its applications in dynamic connectivity, flows, and other areas. Delve into the research presented by Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak from various institutions. Learn about dynamic connectivity, the definition of balanced cut, two-way reduction, and the competition game. Gain insights into the embedding algorithm and its implications for solving complex graph problems. Understand how this research contributes to advancements in computer science and algorithm design.
Syllabus
Introduction
Dynamic Connectivity
Defining Balanced Cut
Two Way Reduction
Competition Game
Summary
Embedding
Algorithm
Conclusion
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