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.
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond
Overview
Syllabus
Introduction
Dynamic Connectivity
Defining Balanced Cut
Two Way Reduction
Competition Game
Summary
Embedding
Algorithm
Conclusion
Taught by
IEEE FOCS: Foundations of Computer Science
