7 citations · 15 across the 8 of their papers we have counts for
Showing 2026Show all
3 papers · 1 filter
cs.DS2026
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…
cs.CC2026
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…
stat.ML2026
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…