7 citations · 15 across the 8 of their papers we have counts for
5 papers · 1 filter
Oracle Efficient Online Multicalibration and Omniprediction
Sumegha Garg, Christopher Jung, Omer Reingold +1
A recent line of work has shown a surprising connection between multicalibration, a multi-group fairness notion, and omniprediction, a learning paradigm that provides simultaneous…
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…
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…
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…