Information Theory in Computational Complexity IV
summary
Shows the exact equivalence between formula depth and communication cost via the Karchmer–Wigderson game and uses that to prove a concrete lower bound: the monotone formula depth for the matching-on-3n-vertices function is monotone depth Ω(n). The proof builds graph gadgets from DISJOINTNESS, reduces to a vertex-cover vs. matching instance, adds shared randomness (random permutations) to turn a deterministic protocol into a randomized one, and uses the augmented INDEX lower bound to derive a streaming-space lower bound of about Ω((log n)^2).
AI-written summary · about
chapters (6)
- 0:00Introduction
- 2:22Formula complexity and streaming
- 13:41Monotone depth for matching
- 27:19Disjointness to matching
- 53:16Streaming space lower bounds
- 1:07:45Q&A
related talks
27mInformation Complexity for Multi-Party NIH Communication
34mOn the Communication Complexity of Sparse Set Disjointness
36mExponential Separation of Information and Communication
33mWelfare Maximization with Limited Interaction: Information and Communication in Economics
01h 08mThe Simple, Little and Slow Things Count: On Parameterized Counting Complexity
55mLower Bounds for Subgraph Isomorphism and Consequences in First-Order Logic
33mLucky Talk: Exponential Separation of Information and Communication
36mRelative Discrepancy Does Not Separate Information and Communication Complexity