Asymptotically Tight Bounds on the Time Complexity of Broadcast and its Variants in Dynamic Networks
summary
Proves that broadcast, k‑broadcast and cover‑of‑size‑k in synchronous adversarial dynamic networks all have asymptotically tight linear worst‑case time. Upper bounds use a bipartite graph linking IDs to rounds and counting degrees to get a 2.4n upper bound (more simply O(n)), while lower bounds include a ~1.5n construction and trivial chain examples. k‑cover analysis runs time backwards, derives constraints giving delta_i = n/i^2 and sums to O(n), and a simple forest construction yields Ω(n−k).
AI-written summary · about
chapters (15)
- 0:00Introduction
- 1:14Model
- 3:27Objective
- 4:22Broadcast on Trees
- 6:07Broadcast Automated Trees
- 6:55Main Observation
- 9:03Graph
- 10:39Observation
- 12:57Lower Bound
- 13:27Key Broadcast
- 14:15Upper Bound
- 18:51Delta Ice Bound
- 22:02Lower Bounds
- 22:33Recap
- 23:07Conclusion
related talks
46mTiming Matters: Online Dynamics in Broadcast Games
19mDeterministic Dynamic Matching In Worst-Case Update Time
30mOptimal Lower Bounds for Distributed and Streaming Spanning Forest Computation
31mBroadcast Optimal Multi-Party Computation
44mTutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 2 of 2)
27mComputation Over the Noisy Broadcast Channel with Malicious Parties
58mThe Communication Complexity Landscape of Information-theoretic MPC
27mHow to Compress Asymmetric Communication