Fourier Growth of XOR-Fibers of Communication Protocols
summary
Proves a tight O(sqrt{d}) bound for level‑1 Fourier growth of XOR‑fibers and an improved O(d^{3/2}) bound for level‑2, conjecturing an optimal O(d · polylog n) bound. Proof views the protocol and its Fourier spectrum as a martingale, controls quadratic variation via a new spectral notion of k‑wise independence, and gives an adaptive partitioning/cleanup that converts any d‑bit protocol into few spectrally k‑wise independent pieces. Applications: Gap‑Hamming lower bounds and stronger quantum‑vs‑classical separations.
AI-written summary · about
chapters (14)
- 0:00Intro
- 3:25XOR Fibers of Communication Protocols
- 5:13Connections & Motivation
- 6:04XOR Fibers & Parity/Standard Decision Trees
- 6:58XOR Fibers & Quantum-Classical Separations
- 12:13XOR Fibers & the Gap-Hamming Problem
- 14:35Proof Outline
- 19:13Viewing the Communication Protocol as a Tree
- 26:35Restating the Problem Geometrically
- 28:09O(d) Bound using a Per-Rectangle Argument [GRT19]
- 34:22Desired Bound on Step-Sizes
- 36:45Spectrally 2-wise Independence
- 38:04Why is spectral 2-wise Independence useful?
- 45:43Cleaning Large Sets Doesn't Take Too Much Time
related talks
01h 04mExplicit SoS Lower Bounds from (Small-Set) High Dimensional Expanders
48mBlack-Box Separations in Quantum Cryptography
55mFoundations 2
34mHigh-entropy dual functions and locally decodable codes
01h 04mQuantum 1
01h 01mCommunication Complexity, Streaming and Computational Assumptions
46mCryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity
01h 09mWhen Cryptography Meets Modern Channel Coding