A New Information Complexity Measure for Multi-pass Streaming with Applications

Mark Braverman, Sumegha Garg, Qian Li +3

We introduce a new notion of information complexity for multi-pass streaming problems and use it to resolve several important questions in data streams. In the coin problem, one se…