On the Communication Complexity of Sparse Set Disjointness
summary
Establishes tight trade-offs for k-sparse set disjointness: a simple bias-tweak of the Håstad–Wigderson-style protocol yields O(k) communication and log k rounds reduced to log k (iterated logarithm) rounds with exponentially small error, and players can learn the intersection with no extra cost. Proves matching lower bounds: any protocol with fewer than log k rounds must pay roughly k·r·(iterated-log k) bits, using reductions from an OR-of-Equalities and information-theoretic compactness arguments.
AI-written summary · about
chapters (11)
- 0:00Start
- 0:39Model considered
- 2:03main examples
- 3:35sparse set disjointness
- 6:22Håstad-Wigderson protocol for SD
- 6:44Sağlam - T improvement
- 14:39Analysis of the Håstad-Wigderson protocol
- 17:28protocol with fewer rounds
- 25:14Protocol for finding the intersection
- 25:37Exists-equal problem
- 27:08Lower bound proofs
related talks
01h 09mInformation Theory in Computational Complexity IV
01h 08mThe Simple, Little and Slow Things Count: On Parameterized Counting Complexity
01h 04mInformation Theory in Computational Complexity I
01h 07mWhere the Hard Things Are
01h 17mInapproximability of Constraint Satisfaction Problems V
01h 00mAverage-case Complexity for Polynomials, and All That
27mA Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion
01h 01mCoding for Modern Distributed Storage Systems I