Tribes is Hard in the Message Passing Model
summary
Shows that Tribes in the coordinator (star) message‑passing model has randomized communication Theta(nk) for the typical setting m = l = √n, so the naive everyone sends to coordinator protocol is essentially optimal. Proof builds a bespoke input distribution with coordinator‑owned switches (m, z, w), extends Braverman et al.’s information‑complexity machinery, introduces a partial information cost and proves a direct‑sum for two‑bit Disjointness instances. Technique lifts to arbitrary graphs, giving cost ≈ n times the terminals’ Steiner tree size.
AI-written summary · about
chapters (16)
- 0:00Intro
- 0:29Multi-party communication
- 2:29The Star Topology
- 4:15A Warm-Up Example
- 8:38Randomized Lower Bounds
- 10:49One-Bit Output
- 11:45Set-Disjointness
- 15:16Rest of the Talk
- 16:35Two Protocols for DISJ
- 20:19Information Measure
- 22:24Input Distribution
- 25:28Distribution for Tribes
- 26:55Information Cost of Tribes
- 28:22Disjointness Supported on 1's
- 30:55Putting Together
- 31:41General Topology.
related talks
58mThe Communication Complexity Landscape of Information-theoretic MPC
01h 08mSelf-stabilizing Population Protocols
42mStochastic reasoning in decentralised systems
46mTiming Matters: Online Dynamics in Broadcast Games
36mCommunication Patterns in Organic Networks
31mNear-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems
24mGang Scheduling for Llama
19mThe Time Complexity of Consensus Under Oblivious Message Adversaries