On Parallelizing Streaming Algorithms
summary
Shows a direct-sum lower bound for parallel streaming: for IID streams computing k independent copies requires about k times the average memory under a standard average-memory measure, assuming single-stream memory m is large relative to n. Proof finds one stream with tiny transitional information content, embeds the hard single stream among random streams, and uses common-information sampling (Harsha et al., Braverman–Garg) to compress information into short encodings, yielding a compression lemma (≈n·information blowup) that is nearly tight. Open problems: compress to cumulative information content and improve parameters.
AI-written summary · about