Noisy Connections: A Survey of Interactive Coding and Its Borders with Other Topics
summary
Surveys interactive coding results: Schulman (1992) shows you can tolerate a constant fraction of adversarial bit flips with only a constant communication blowup if you use combinatorial tree codes, but explicit efficient decoding is unknown. Later constructions replace long tree codes with short chunk + hash schemes (Bürg/Ka̧łai 2012) that are polynomial-time and succeed with high probability for, say, 10% errors on a 100-bit run, and Hopcroft-style refinements (2014) shrink chunks and hashes to constant size. Works build concrete protocols that preserve correctness and, with extra care (fresh randomness, amplification), preserve soundness for IP=PSPACE; information-theoretic secrecy/knowledge preservation remains impossible at constant error rates.
AI-written summary · about
chapters (24)
- 0:00Introduction
- 1:10Twoparty computation
- 3:07Constant error rate
- 3:55Protocol tree
- 4:38Depth
- 7:23Pebble Movement
- 10:14Tree Coats
- 12:53Tree Codes
- 18:00Error Correction
- 18:37Labeling
- 19:55Trees
- 21:01Decoding
- 23:28Good Events
- 24:20Progress
- 24:58Decoding Error
- 28:42Bad Events
- 29:10Hold or Back
- 33:20Bad News
- 35:45Collision Resistant Hash
- 36:14The Problem
- 43:26The Surprise
- 44:12Hash Collisions
- 50:43Knowledge Preservation
- 53:42Information Preservation
related talks
44mCoding Theory in Almost Linear Time and Sublinear Space
40mBinary Codes with Resilience Beyond 1/4 via Interaction
01h 01mCommunication Complexity, Streaming and Computational Assumptions
01h 00mError-Correcting Codes That Enable Efficient SNARKs
32mComputational Wiretap Coding from Indistinguishability Obfuscation
35mBinary Error Correcting Codes with Minimal Noiseless Feedback
19mError Correcting Codes for Uncompressed Messages
01h 08mSecure Computation 1