Information Theory in Computational Complexity I
summary
Defines protocols as binary trees and proves for the equality function that deterministic complexity = N by showing every 1 on the N×N matrix needs its own monochromatic rectangle. Uses public randomness to hash N-bit inputs (Hadamard/any code) so public-coin O(1) (O(log 1/ε) to reduce error) suffices, and gives the standard simulation that a public-coins protocol becomes private-coin with +O(log N) overhead. Presents a randomized O(log N)-bit procedure (random-walk plus backtracking) to locate the first differing bit, improving the naive O(log N · log log N).
AI-written summary · about
chapters (6)
- 0:00Introduction to the course
- 2:00Deterministic protocol model
- 10:45Equality and rectangles
- 26:13Randomized protocol models
- 31:24Randomized protocols for equality
- 50:10Advanced protocols and drift
related talks
25mInternal Compression of Protocols to Entropy
27mInformation Complexity for Multi-Party NIH Communication
01h 17mTutorial on Coding for Interactive Communication: Introduction and Overview
33mLucky Talk: Exponential Separation of Information and Communication
33mWelfare Maximization with Limited Interaction: Information and Communication in Economics
29mAssumptions in cryptography and complexity theory
01h 19mTutorial on Efficient Coding for Interactive Communication via List Decoding
36mExponential Separation of Information and Communication