7 citations · 15 across the 8 of their papers we have counts for
4 papers · 1 filter
Query Lower Bounds for Correlation Clustering under Memory Constraints
Sumegha Garg, Songhua He, Periklis A. Papakonstantinou
This work initiates the study of memory-query tradeoffs for graph problems, with a focus on correlation clustering. Correlation clustering asks for a partition of the vertices that…
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…
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG
Sumegha Garg, Pravesh K. Kothari, Ran Raz
In this work, we establish lower-bounds against memory bounded algorithms for distinguishing between natural pairs of related distributions from samples that arrive in a streaming…
The space complexity of mirror games
Sumegha Garg, Jon Schneider
We consider a simple streaming game between two players Alice and Bob, which we call the mirror game. In this game, Alice and Bob take turns saying numbers belonging to the set $\{…