Counting Distinct Elements in the Message Passing Model
summary
Proves an Omega communication lower bound: the randomized distributional sum‑disjointness task in the k‑party point‑to‑point model requires omega(n k) bits by embedding a Bernoulli gap threshold problem, using the rectangle property to show bits stay independent conditioned on the transcript, an unbiased conditional expectation lemma and a “lots of randomness after conditioning” count to force anti‑concentration, then reducing to two‑party disjointness to contradict known bounds and extend to a k/epsilon^2 lower bound for distinct‑elements.
AI-written summary · about
chapters (13)
- 0:00Intro
- 0:25Model Overview
- 1:09The Coordinator
- 1:59Problems
- 7:16Property of Communication
- 10:09Proof
- 10:42Unbiased conditional expectation
- 12:05Sampling an input
- 15:50A simple extension
- 16:34Sum disjoint
- 20:41Reducing two players
- 22:34Other techniques
- 23:57Accounting distinct roots
related talks
27mOn Distributed Differential Privacy and Counting Distinct Elements
31mBroadcast Optimal Multi-Party Computation
10mQuery, Communication and Discrepancy
38mLower Bounds for Off-Chain Protocols: Exploring the Limits of Plasma c
01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
20mBalanced Allocations with Incomplete Information: The Power of Two Queries
30mOn the Optimal Round Complexity of Multi-Party Computation in the Plain Model
30mOptimal Lower Bounds for Distributed and Streaming Spanning Forest Computation