Lucky Talk: Exponential Separation of Information and Communication
summary
Constructs a boolean function on inputs that label every vertex of a complete binary tree with 2^{4^k} multilayers, grouping every 100k levels into a multilayer. A vertex is typical if the path into its multilayer has ≥80% correct directions. Distribution: before the chosen noisy multilayer nodes are identical, that multilayer is fully noisy, and below it a carefully chosen bursting noise tapestry makes non‑typical subtrees noisy. The function hides a random bit b by xoring b into Bob’s leaf bits; any typical leaf sums to b. A randomized protocol that at each vertex sends the true bit with 90% (flip with 10%) reaches a typical leaf with high probability, yields information cost O(k) (only ~100k noisy vertices leak bits), but any communication protocol needs double‑exponential length (2^{2^{Ω(k)}}). An abort rule on detecting the bursting noise (via an exponential disagreement count) removes a tiny failure case.
AI-written summary · about
chapters (9)
- 0:00Introduction
- 1:25Example
- 2:22Typical Vertex
- 4:49Bursting Noise
- 7:37The Search Problem
- 10:45The Boolean Function
- 17:04The Protocol
- 28:17The Bug
- 30:37Questions
related talks
01h 04mInformation Theory in Computational Complexity I
01h 09mInformation Theory in Computational Complexity IV
01h 00mAverage-case Complexity for Polynomials, and All That
24mBlock Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing
01h 10mDistribution Estimation and Applications I
01h 07mWhere the Hard Things Are
32mA Finite Alternation Result for Reversible Boolean Circuits
01h 05mLifting to Parity Decision Trees via Stifling (with applications to proof complexity)