Error Correction for Streaming Messages
summary
Provides an explicit encoding enc(x) of length about n^2 that lets Bob recover f(x) (e.g. y·x) in space s·polylog(n) even under adversarial noise up to δ = 1/4 − ε, with high probability. Construction composes locally decodable codes at the leaves, repeats subcomputations with polylog n leaves and takes majority to prevent targeted corruption, and achieves general deterministic f at cost ~n^4. Communication and space bounds are proved and several tighter bounds remain open.
AI-written summary · about
chapters (5)
- 0:00Problem introduction
- 2:29Theorem and goals
- 7:25Using locally decodable codes
- 11:55Recursive tree construction
- 19:58Open problems and discussion
related talks
01h 03mAdversarially Robust Streaming Algorithms
27mComputation Over the Noisy Broadcast Channel with Malicious Parties
19mSecure Distributed Network Optimization Against Eavesdroppers
26mA Framework for Adversarial Streaming via Differential Privacy and Difference Estimators
30mNon-malleable Codes Against Constant Split-state Tampering
54mFully Homomorphic Encryption
34mCapacity Inversion and MPC over Elastic Noisy Channels
18mDifferentially Private Continual Releases of Streaming Frequency Moment Estimations