Information Theory in Computational Complexity II
summary
Proves that the randomized communication complexity of Disjointness is Ω(N) by reducing the N-bit problem to a single-bit AND and lower-bounding the information transfer per coordinate. The proof finds a weak coordinate with information ≤ O(C/N), embeds the AND there by fixing the other bits from a carefully chosen activation pattern, and uses the information complexity framework plus the Hellinger/Bhattacharyya distance and the rectangle product structure of transcripts to force a contradiction unless C = Ω(N).
AI-written summary · about