STOC2024
A New Information Complexity Measure for Multi-pass Streaming with Applications
Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, Jiapeng Zhang
摘要
We introduce a new notion of information complexity for multi-pass streaming problems and use it to resolve several important questions in data streams.