7 citations · 9 across the 2 of their papers we have counts for
6 papers
Memory-Sample Lower Bounds for Learning Parity with Noise
Sumegha Garg, Pravesh K. Kothari, Pengda Liu +1
In this work, we show, for the well-studied problem of learning parity under noise, where a learner tries to learn from a stream of random linear…
The Role of Randomness and Noise in Strategic Classification
Mark Braverman, Sumegha Garg
We investigate the problem of designing optimal classifiers in the strategic classification setting, where the classification is part of a game in which players can modify their fe…
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…
Tracking and Improving Information in the Service of Fairness
Sumegha Garg, Michael P. Kim, Omer Reingold
As algorithmic prediction systems have become widespread, fears that these systems may inadvertently discriminate against members of underrepresented populations have grown. With t…
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 $\{…
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…