7 citations · 15 across the 8 of their papers we have counts for
13 papers
Systematic Data Structure Lower Bounds via the Query-with-Sketch Model
Sumegha Garg, Songhua He, Yuanzhi Li +2
We study data structure lower bounds for the Approximate Matrix Powering (AMP) problem. Given a substochastic, symmetric matrix and parameters…
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…
Online Learning with Limited Information in the Sliding Window Model
Vladimir Braverman, Sumegha Garg, Chen Wang +2
Motivated by recent work on the experts problem in the streaming model, we consider the experts problem in the sliding window model. The sliding window model is a well-studied mode…
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…
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…
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…
Network coding in undirected graphs is either very helpful or not helpful at all
Mark Braverman, Sumegha Garg, Ariel Schvartzman
While it is known that using network coding can significantly improve the throughput of directed networks, it is a notorious open problem whether coding yields any advantage over t…
New security notions and feasibility results for authentication of quantum data
Sumegha Garg, Henry Yuen, Mark Zhandry
We give a new class of security definitions for authentication in the quantum setting. These definitions capture and strengthen existing definitions of security against quantum adv…