Exponential Separation of Information and Communication

on YouTube ↗36m

" summary

Claim: there is an explicit search problem and distribution mu for which the information cost O(k) vs communication ≥ 2^k gap holds, so transcripts cannot always be compressed to their information. Construction uses a huge layered binary tree called the bursting noise game, with nonproduct noisy layer selection and triple‑exponential input size. Lower bound uses a new technique called relative discrepancy. Corollary: strong direct sum fails; existing compression gives at best 2^{O(info)} so the separation is tight.

AI-written summary · about

" chapters (11)

1. 0:00Introduction
2. 0:40Data Compression
3. 1:34Interactive Compression
4. 2:57Communication Complexity
5. 6:57Information Cost Formula
6. 16:51Exponential Separation
7. 20:31Direct Sum
8. 23:49Example
9. 26:06Distribution
10. 27:34Typical Vertex
11. 31:27Search Problem

" related talks

• 01h 09mInformation Theory in Computational Complexity IVJaikumar Radhakrishnan · Information Theory Boot Camp 2015
• 01h 04mInformation Theory in Computational Complexity IJaikumar Radhakrishnan · Information Theory Boot Camp 2015
• 52mThe Mystery of the Missing StringRyan Williams · Lower Bounds, Learning, and Average-Case Complexity
• 51mAllender's Conjecture and its Impacts on Meta-ComplexityShuichi Hirahara · Lower Bounds, Learning, and Average-Case Complexity
• 01h 00mAverage-case Complexity for Polynomials, and All ThatEmanuele Viola · Lower Bounds, Learning, and Average-Case Complexity
• 24mBlock Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for TuringRan Raz, Kunal Mittal · ITCS 2021
• 23mHow to Cheat at “Who Wants to Be a Millionaire?” (and Show Non-Hardness of GapMCSP)Neekon Vafa · Lower Bounds, Learning, and Average-Case Complexity
• 01h 10mDistribution Estimation and Applications IAlon Orlitsky · Information Theory Boot Camp 2015