7 citations · 15 across the 8 of their papers we have counts for
Showing 2017Show all
2 papers · 1 filter
cs.CC2017
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 $\{…
cs.LG2017
Extractor-Based Time-Space Lower Bounds for Learning
Sumegha Garg, Ran Raz, Avishay Tal
A matrix corresponds to the following learning problem: An unknown element is chosen uniformly at random. A learner tries to learn $x…