Communication Complexity, Streaming and Computational Assumptions
summary
Assuming polynomial-time adversaries, the work shows concrete reductions: a simultaneous-message equality protocol that beats the sqrt(n) bound implies a distributional collision-resistant hash functions family that compresses n to λ so communication drops to about sqrt(λ) (interactive log n → log λ similarly); conversely CRH yield succinct protocols. In a stateful free-talk model a c-bit protocol with error ~2^{-0.7c} converts into a secret-key agreement (via sampling multisets and Holenstein-style amplification); results need rushing/patient adversary models and currently only reach up to c ≈ log log n.
AI-written summary · about
chapters (9)
- 0:00Introduction and scope
- 3:36Communication complexity
- 11:08Simultaneous message model
- 15:24Preset randomness model
- 22:02Hardness assumptions
- 27:35Constructing hash functions
- 35:15Characterizing multi-sets
- 44:29Stateful free talk model
- 52:30Protocol conversion
related talks
01h 09mNoisy Connections: A Survey of Interactive Coding and Its Borders with Other Topics
01h 08mSecure Computation 1
58mThe Communication Complexity Landscape of Information-theoretic MPC
01h 03mClosing Keynote Day 2
40mCryptography in Distributed Systems
01h 06mDelegating Computation II
29mTowards Scalable Constant-Round MPC from Minimal Assumptions via Round Collapsing
01h 00mSecure Computation 3