3 papers
cs.CC2026
A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
Sumegha Garg, Jabari Hastings, Chirag Pabbaraju +1
We present a unified framework for proving memory lower bounds for multi-pass streaming algorithms that detect planted structures. Planted structures -- such as cliques or biclique…
cs.IT2025
Testing Tensor Products of Algebraic Codes
Sumegha Garg, Madhu Sudan, Gabriel Wu
Motivated by recent advances in locally testable codes and quantum LDPCs based on robust testability of tensor product codes, we explore the local testability of tensor products of…
cs.LG2025
The Space Complexity of Learning-Unlearning Algorithms
Yeshwanth Cherapanamjeri, Sumegha Garg, Nived Rajaraman +2
We study the memory complexity of machine unlearning algorithms that provide strong data deletion guarantees to the users. Formally, consider an algorithm for a particular learning…