Information Complexity for Multi-Party NIH Communication
summary
Proves that k‑party number‑in‑hand disjointness on n coordinates has an Ω(n log k) communication lower bound under shared blackboard by first applying a direct‑sum to one‑bit AND and then showing that each coordinate forces the transcript to reveal the identity of a player missing that bit, costing Θ(log k) information. The hard distribution picks a special player z with a zero and other players zero independently with probability 1/k. Shows an Ω(k / log k) gap between communication and external information and limits on compressing protocols.
AI-written summary · about
chapters (14)
- 0:00Start
- 0:31MULTI-PARTY NUMBER-IN-HAND
- 0:50MULTI-PARTY COMMUNICATION PROTOCOLS
- 2:06LOWER BOUNDS IN DISTRIBUTED COMPUTING
- 5:07ASIDE: 2-PARTY REDUCTIONS
- 6:20SET DISJOINTNESS
- 7:09REDUCTION FROM DISJ TO GRAPH DIAMETER
- 9:14COMMUNICATION COMPLEXITY OF DISJ
- 13:08INFORMATION COMPLEXITY OF DISJ
- 14:34INFORMATION COST FOR MULTI-PARTY PROTOCOLS
- 16:58DIRECT SUM PROOF OUTLINE (CSWY'01,BJKS'04)
- 21:40PUTTING THE PIECES TOGETHER
- 22:16INCOMPRESSIBILITY FOR EXTERNAL INFORMATION
- 25:04AMORTIZED COMPRESSION
related talks
01h 09mInformation Theory in Computational Complexity IV
01h 04mInformation Theory in Computational Complexity I
24mBlock Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing
01h 00mAverage-case Complexity for Polynomials, and All That
49mHard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness
51mAllender's Conjecture and its Impacts on Meta-Complexity
59mRandom log(n)-CNF are Hard for Cutting Planes (Again)
27mA Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion