Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems
summary
Deterministic distributed algorithms implement dynamic symmetry-breaking with near-optimal message costs: Delta+1 coloring and maximal matching use O(m^{1/2}) messages and O(1) rounds worst-case, three-halves approx matching uses O(m^{1/2}) amortized messages and O(log Δ) rounds, and maximal independent set uses O(m^{2/3} log^2 n) amortized messages and O(log^2 n) amortized rounds. Techniques include dynamic edge orientation, high-degree/low-degree partitioning via a local six-hop neighborhood, local restarts and a small-diameter static MIS subroutine (CPS-20); algorithms handle adaptive adversaries and match centralized update times up to polylog factors.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 0:17Static Algorithms
- 1:35Dynamic Algorithms
- 7:39Challenges
- 17:02Two Challenges
- 18:13Distributed Algorithm
- 20:19Important Things to Consider
- 22:38Solution to Challenge 1
- 23:55Solution to Challenge 2
- 29:10Final Thoughts
related talks
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
46mTiming Matters: Online Dynamics in Broadcast Games
58mExponential-Time Algorithms
30mOptimal Lower Bounds for Distributed and Streaming Spanning Forest Computation
01h 00mHardness for Dynamic Problems; Conclusion and Future Research
44mTutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 2 of 2)
29mFirst Order Methods for Distributed Network Optimization
26mOn the O(1/k) Convergence of the Asynchronous Distributed Alternating Direction Method of Mult...